一个正整数可以表示为连续正整数之和当且仅当它不是 2 的幂
尝试一下-检查连续数字和-哈希编程-PythonTip学编程
def check_consecutive_sum(n):
# 此处写代码
return (n&(n-1))!=0 and n!=0
为什么这样工作？
对于2的幂：
n = 8 = 1000 (二进制) n-1 = 7 = 0111 (二进制) n & (n-1) = 1000 & 0111 = 0000 = 0
对于不是2的幂：
n = 6 = 0110 (二进制) n-1 = 5 = 0101 (二进制) n & (n-1) = 0110 & 0101 = 0100 = 4 ≠ 0
数学原理
这个技巧基于：
-
2的幂的二进制形式是
1000...0（只有一个1） -
n-1的二进制形式是0111...1（所有低位都是1） -
两者进行按位与运算结果为0
在连续和问题中的应用
在连续和问题中，这个技巧用于快速判断：
-
如果是2的幂：
(n & (n-1)) == 0→ 不能表示为连续正整数之和 -
如果不是2的幂：
(n & (n-1)) != 0→ 可以表示为连续正整数之和