首页 > 其他 > 详细

LeetCode:Number of 1 Bits

时间:2015-03-22 14:59:50      阅读:123      评论:0      收藏:0      [点我收藏+]

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 };

个人猜测:最后一种方法,因为使用了引用传递,免了返回结果时,变量的复制开销。

 

LeetCode:Number of 1 Bits

原文:http://www.cnblogs.com/coder-chen/p/4357276.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!