15.二进制中1的个数

题目描述

输入一个整数&＃xff0c;输出该数二进制表示中1的个数。其中负数用补码表示。

补码说明&＃xff1a;

正数的补码和原码表示相同

负数的补码为&＃xff08;正数取反后加1&＃xff0c;或者负数的原码除符号位外取反&＃xff0c;然后加1&＃xff09;&＃xff0c;如-5对应正数5&＃xff08;00000101&＃xff09;→所有位取反&＃xff08;11111010&＃xff09;→加1(11111011)

0的补码还是0

左移运算&＃xff1a;m<

右移运算&＃xff1a;m>>n&＃xff0c;如果是无符号数&＃xff0c;则用0补充最左边的n位&＃xff1b;如果是有符号数&＃xff0c;正数的话在最左边补n个0&＃xff0c;负数的话在最左边补n个1.

此题Python有坑&＃xff01;&＃xff01;

思路1&＃xff1a;让n和1做位与运算&＃xff0c;如果结果大于0&＃xff0c;则说明该位是1&＃xff0c;计数加1。然后把1左移&＃xff0c;再次和n做位与运算。直到flag为0程序结束。&＃xff08;为什么不让n进行右移呢&＃xff1f;如果n是负数&＃xff0c;让n进行右移&＃xff0c;那么左边就会一直补充1&＃xff0c;相同的终止条件的话可能陷入死循环&＃xff09;

C&＃43;&＃43;题解&＃xff1a;

class Solution {
public:int NumberOf1(int n) {int count&＃61;0;unsigned int flag&＃61;1;while(flag){if(n&flag) //或者 if((n&flag)&＃61;&＃61;flag)count&＃43;&＃43;;flag&＃61;flag<<1;}return count;}
};

思路2&＃xff1a;按照n&(n-1)会使得n最右边的那个1变成0&＃xff0c;这样做&＃xff0c;计数n变到0所需的次数就是n中1的个数。

C&＃43;&＃43;题解&＃xff1a;

class Solution {
public:int NumberOf1(int n) {int count&＃61;0;while(n){n&＃61;n&(n-1);count&＃43;&＃43;;}return count;}
};