剑指offer 面试题10:二进制中1的个数
二进制中1的个数
提交网址: http://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&tqId=11164
参与人数:7222 时间限制:1秒 空间限制:32768K 题目描述 输入一个整数,输出该数二进制表示中1的个数。(温馨提示: 计算机中负数用补码表示。)
先贴上代码,然后来详细介绍原理哈...
AC代码:
#include<iostream>
using namespace std;
class Solution {
public:
int NumberOf1(int n) {
int count=0;
while(n != 0)
{
n=n&(n-1); // 每进行一次,将最右侧存有1的bit的值置为0,直到全0,退出循环
count++;
}
return count;
}
};
// 以下为测试
int main()
{
int num1=-6;
int num2=0;
int num3=-1;
int num4=+255;
int num5=7;
Solution sol;
cout<<sol.NumberOf1(num1)<<endl; // -6对应的32bit中,有2位是0,其余都是1
cout<<sol.NumberOf1(num2)<<endl;
cout<<sol.NumberOf1(num3)<<endl;
cout<<sol.NumberOf1(num4)<<endl;
cout<<sol.NumberOf1(num5)<<endl;
return 0;
}
代码中的 n&(n-1) 是什么意思?
计算机组成原理 背景知识:
计算机中如何表示负数?
设计计算机的人设想,把最高位作为符号位,0表示正数,1表示负数,于是原码诞生了。计算机中8位二进制数(原码)的表示范围如下: 负数:1 111 1111 ~ 1 000 0000 (-127 ~ -0),正数:0 000 0000 ~ 0 111 1111 (0 ~ 127) 但是如果在计算机中像这样用原码表示负数,那么数的相加减就很不方便了。因此计算机中有符号数都是用补码形式表示,此点需时刻牢记于心! 补码怎么计算?
1、正数:原码和补码一致 2、负数:原码除符号位外后按位取反,然后加1 (从补码求原码的方法:符号位除外,先减1,再按位取反。) 3、[+0]补=[-0]补=0x00000 如果用4个字节来表示-7~8,则-3的在计算机中的表示是1101(原码为1011),则-2的在计算机中的表示是1110(原码为1010),-1在计算机里用二进制表示就是全1,4位2进制为1111,16进制为:0xFFFFFF 1. 如果n>0,正数的补码和原码一致 (1)当n为正奇数时(n的二进制表示的末位为1): n: xxxxxxxx1 n-1: xxxxxxxx0 n&(n-1): xxxxxxxx0 n&(n-1)相当于去掉n的二进制表示中最右边的一个1。 (2)当n为正偶数时(n的二进制表示的末位为0): n: xxxxx1000 n-1: xxxxx0111 n&(n-1): xxxxx0000 n&(n-1)相当于去掉n的二进制表示中最右边的一个1。 2. 如果n<0 (3)当n为负奇数时,比如-1: n=-1: 1111 n-1=-2: 1010 n&(n-1): 1010 n&(n-1)相当于去掉n的二进制补码中最右边的一个1。 (4)当n为负的偶数时,比如-2: n=-2: 1010 n-1=-3: 1101 n&(n-1): 1000 n&(n-1)相当于去掉n的二进制补码中最右边的一个1。 3. 如果n=0
(5) 当n=0时 n=0: 0000 n-1=-1: 1111 n&(n-1): 0000 n&(n-1)相当于去掉n的二进制补码中最右边的一个1(或 不处理,因为0的二进制补码中没有1)。
如,9999 的二进制表示为: 0010 0111 0000 1111,共有8个1.
综上(1)、(2)、(3)、(4)、(5)可知,n&(n-1)等价于去掉有符号整数整数n的二进制补码中最右边的一个1,无论n为正、为负或为0 .
另一相关的位运算知识点:
n=n&(n-1)==0 可以用来判断n是否为2的幂次方(即:n中除符号位以外只有一个1,其他bit均为0)
相关链接:
c++ - How does this line work ? n=n&(n-1); - Stack Overflow http://stackoverflow.com/questions/15370250/how-does-this-line-work-n-nn-1
bit manipulation - What do (n&(n-1))==0 and n&(n-1)==0 do in C++? - Stack Overflowhttp://stackoverflow.com/questions/21234217/what-do-nn-1-0-and-nn-1-0-do-in-c
java - Why if (n & -n) == n then n is a power of 2? - Stack Overflow http://stackoverflow.com/questions/7405438/why-if-n-n-n-then-n-is-a-power-of-2