【面试题010】二进制中1的个数
二进制中1的个数
这个世界上面有10种人，一种人知道二进制，而另一种人不知道二进制……呵呵……
输入一个整数，输出该数二进制表示中1的个数。
方法一：
1除了最右边的一位之外，其他所有位置都是0，如果一个整数与1做与运算的结果是1，表示该整数最右边一位是1，否则是0，
然后这个数字在右移一位，如此循环，可得正解；
数学上除以2，和向右移一位是等价的，但是在计算机学科移位的效率比除法高多了；
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream>
using namespace std; int NumberOf1( int n) { int count = 0; while(n) { if(n & 1) { count ++; } n = n >> 1; } return count; } int main() { cout << NumberOf1( 10) << endl; return 0; } |
注意是，用这种方法没有办法解决输入的整数是负数的问题，如果是负数就死循环了。
方法二：
为了避免负数的移位问题，其实我们可以把1左移一位，这样子就可以判断n的次低位是不是1……
这样子反复左移，每次都能判断n的其中一位是不是1，
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream>
using namespace std; int NumberOf1_1( int n) { int count = 0; while(n) { if(n & 1) { count ++; } n = n >> 1; } return count; } int NumberOf1( int n) { int count = 0; unsigned int flag = 1; while(flag) { if(n & flag) { count ++; } flag = flag << 1; } return count; } int main() { cout << NumberOf1_1( 10) << endl; cout << NumberOf1( 10) << endl; return 0; } |
方法三：
n减去一个数(1)，如果n不等于0的话， 本质就是，把n最右边的1变成0，如果1的右边还有其他0的话，把这些其他的0都变成1；
而这个1他左边的数字都保持不变；
我们发现一个问题，n&(n-1)的结果就是去掉n最后的那个1的过程，太好了……
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream>
using namespace std; int NumberOf1_1( int n) { int count = 0; while(n) { if(n & 1) { count ++; } n = n >> 1; } return count; } int NumberOf1_2( int n) { int count = 0; unsigned int flag = 1; while(flag) { if(n & flag) { count ++; } flag = flag << 1; } return count; } int NumberOf1( int n) { int count = 0; while(n) { ++ count; n = (n - 1) & n; } return count; } int main() { cout << NumberOf1_1( 10) << endl; cout << NumberOf1_2( 10) << endl; cout << NumberOf1( 10) << endl; return 0; } |
运行结果：
2
2
2
Makefile:
|
1
2 3 4 5 6 7 8 9 10 11 12 |
.PHONY:clean
CPP=g++ CFLAGS=-Wall -g BIN=test OBJS=NumOf1.o LIBS= $(BIN):$(OBJS) $(CPP) $(CFLAGS) $^ -o $@ $(LIBS) %.o:%.cpp $(CPP) $(CFLAGS) -c $< -o $@ clean: rm -f *.o $(BIN) |
转播
