位运算

1. 求某个数是不是2的N次方，要求复杂度为O(1)

漫画：判断2的乘方

• 用查表的方法是复杂度O（lgn），n为数字大小
• 用递归的方法是复杂度O（n）,n为数字位数

//先找到1，在判断
bool Is2Power(UINT32 num)
{
    if(num==0)
    {
        return true;
    }

    if(num%2==0)
    {
        return Is2Power(num>>2);
    }
    else
    {
        if((num>>2)==0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}

• 用位运算n&(n-1)得到复杂度为O(1)

2. 实现一个方法，求出一个正整数转换成二进制后的数字“1”的个数。要求性能尽可能高。

NSInteger value = 111;  
NSInteger count = 0;  
while (value) {  
    NSLog(@"%ld",value&1);  
    int x = value&1;  
    if (x == 1) count++;  
    value = value>>1;  
}  

3. 其中的扩展题目1