此题解重点在于详细解释了lowbit函数 也只有这个需要仔细解释了叭
ps: 如看完注释还是不太理解的读者 可以再康康代码下新加的两点补充
C ++ 代码如下:
#include <iostream>
using namespace std;
int n;
/* lowbit()函数 作用:返回 x 的最后一位 1 (二进制的形式下)
应用:也是树状数组常用操作之一
实现原理 :-x = ~x + 1;
而 ~x 后 最后一个1后取反为0,其后的所有0(如果有的话)都变为1
故再 +1 后 后面所有取反后的 1 (如果没有则忽略此步骤)
会从最后一个1开始向前进位且该位的数变为 0(即恢复原位)
直至进位到原数最后一个 1 取反后的 0 处停止向前进位。(也相当于恢复原位)
“ps:即使后面没有0也不会影响最后结果,只是相当于省掉了这样一个后面的数进位恢复原位的过程”
至此 :从原数最后一个 1 一直到最后的位置上的数每个位置上的数都恢复到了原来的数,
而原数最后一个 1 之前的所有数都仍然保留取反后的情况
(由上面进位过程得:进位到原数最后一个1的位置就停下进位了)
所以最后 x & -x 的值就是 x 的最后一位1所形成的值
(因为由上述分析得知 ~x + 1 后的数除了原数最后一个1的位置和原数一样都为1,
其余的1的位置全都保留取反后的情况,即为0)
(而 -x = ~x + 1, 所以 x & -x = x & (~x + 1), 按位与之后就得到了x最后一位1的值)
*/
int lowbit(int x) {
return x & -x;
}
int main() {
cin >> n;
while (n -- ) {
int x, ans = 0;
cin >> x;
while (x) x -= lowbit(x), ans ++ ;
// x 每次减去二进制中最后一个 1,故循环结束后减去的次数就为 x 的二进制中 1 的个数
cout << ans << ' ';
}
cout << endl;
return 0;
}
补充:
想了想如果只是单纯的文字解释可能还是有点抽象
于是决定再加上例子补充啦 ~
原始版写的时候我还是第一次写题解(就很简陋也单调 见谅哈~) 所以这次决定加上补充~
咳咳,正文在此:
1、-x = ~x + 1的说明:
1)、从数学角度:
对于一个数x和它的相反数-x,那么我们应该都知道它们俩应该满足条件
x + (-x) = 0
故对于二进制形式下的x来说它也应当满足
x + (-x) = 0...0
(…表示多个)eg:x = 10
则 x 的二进制形式为:$ (1010 )_2 $ ,故需满足 $ (1010)_2 $ + $ (-x)_2 $ = $ (0000)_2 $
所以:$ (-x)_2 $ = $ (0000)_2 $ - $ (1010)_2 $
= $ (0110)_2 $而 ~x = $ (0101)_2 $ ,~x + 1 = $ (0110)_2 $ = $ (-x)_2 $
所以 -x = ~x + 1
2)、从计算机内部存储整数的方式角度:
这个角度就更简单粗暴地好理解啦计算机用补码存储一个整数,而正数的补码是它本身,负数的补码是它的绝对值的补码取反 + 1
2、 lowbit(x)函数的例子演示:
eg: x = 10
则 x 的二进制形式为:$ (1010 )_2 $ –> 故x的最后一位1应为:$ (10)_2 $ ,即 2
取反: ~x = $ (0101)_2 $
再 +1 : ~x + 1 = $ (0110)_2 $而此时 lowbit(x)
= x & -x
= x & (~x + 1)
= $ (1010)_2 $ & $ (0110)_2 $
= $ (0010)_2 $
= 2故做法正确~~
竟然还有这么棒的解析(
哈哈哈 没有没有 有帮助就好~
感谢!!!
负数的补码相当于全部(包括符号位与数值位)取反再加一
唔 是它的绝对值的补码全部取反再加一哦 不过你的意思好像也是这样的~
tql
第一次写题解,唔,因为自己还很菜,所以什么时间复杂度啥的都不知道怎么写,见谅啊,仅仅只是写了刚刚详细分析了lowbit()函数实现的过程~~~希望对看这个的人有所帮助
此次更新了该题解~ 丰富了下注释 并且修饰了整个题解 还在末尾加上了两点补充 希望对看的人有帮助呀
太感谢了
客气啦 有用就行~ 现在都没咋学算法了 估计后面也不会有题解更新了(hhh 虽然好像也没写啥~)