Write a function that takes an unsigned integer and returns the number of ’1‘ bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11‘ has binary representation 00000000000000000000000000001011
, so the function should return 3.
这题比较容易,主要是移位运算符的运用。
使用循环来解决:耗时是18ms
1 int hammingWeight(uint32_t n) { 2 int result=0; 3 for(int i=0;i<32;i++){ 4 if((n&0x01)==1) 5 ++result; 6 n=n>>1; 7 } 8 return result; 9 }
然后通过递归来解决,代码少了,耗时是14ms
1 class Solution { 2 public: 3 int hammingWeight(uint32_t n) { 4 5 return recursion(n,0); 6 } 7 int recursion(uint32_t n,int step){ 8 if(step==32) return 0; 9 if(n&0x01==1) 10 return recursion(n>>1,step+1)+1; 11 else 12 return recursion(n>>1,step+1); 13 } 14 };
使用递归式主要是注意到如何向上一个栈帧传递结果,即return 计算的结果到上一个栈帧;
另外一种递归,使用引用,使得各个栈帧得以共享变量,如下,耗时9ms。直接是第一种方法耗时的一半。
1 class Solution { 2 public: 3 int hammingWeight(uint32_t n) { 4 int result=0; 5 recursion(n,0,result); 6 return result; 7 } 8 void recursion(uint32_t n,int step,int& result){ 9 if(step==32) return; 10 if(n&0x01==1) 11 result++; 12 recursion(n>>1,step+1,result); 13 } 14 };
个人猜测:最后一种方法,因为使用了引用传递,避免了返回结果时,变量的复制开销。
原文:http://www.cnblogs.com/coder-chen/p/4357276.html