n & (n - 1) 抹去最后一个1

2019-01-25  本文已影响0人  Magic11

1、二进制中有多少个1
https://www.lintcode.com/problem/count-1-in-binary/description
描述
计算在一个 32 位的整数的二进制表示中有多少个 1.
您在真实的面试中是否遇到过这个题? 是
题目纠错
样例
给定 32 (100000),返回 1

给定 5 (101),返回 2

给定 1023 (1111111111),返回 10

解题思路:
这种方法速度比较快,其运算次数与输入n的大小无关,只与n中1的个数有关。如果n的二进制表示中有k个1,那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1,同时累加计数器,直至n为0
为什么n &= (n – 1)能清除最右边的1呢?因为从二进制的角度讲,n相当于在n - 1的最低位加上1。举个例子,8(1000)= 7(0111)+ 1(0001),所以8 & 7 = (1000)&(0111)= 0(0000),清除了8最右边的1(其实就是最高位的1,因为8的二进制中只有一个1)。再比如7(0111)= 6(0110)+ 1(0001),所以7 & 6 = (0111)&(0110)= 6(0110),清除了7的二进制表示中最右边的1(也就是最低位的1)

class Solution {
public:
    /*
     * @param num: An integer
     * @return: An integer
     */
    int countOnes(int num) {
        // write your code here
        int count = 0;
        while(num!=0){
            num = num & (num-1);
            count++;
        }
        return count;
    }
};

2、142. O(1)时间检测2的幂次
https://www.lintcode.com/problem/o1-check-power-of-2/description
描述
用 O(1) 时间检测整数 n 是否是 2 的幂次。
O(1) 时间复杂度
您在真实的面试中是否遇到过这个题? 是
题目纠错
样例
n=4,返回 true;

n=5,返回 false.
挑战
O(1) time

public class Solution {
    /**
     * @param n: An integer
     * @return: True or false
     */
    public boolean checkPowerOf2(int n) {
        // write your code here
        if (n <= 0) {
            return false;
        }
        return (n & (n -1)) == 0 ? true : false;
    }
}

3、数 1
https://www.lintcode.com/problem/counting-bits/description
描述
给以 非负 整数 num. 对所有满足 0 ≤ i ≤ num 条件的数字 i 均需要计算其二进制表示 1 的个数并以数组的形式返回
您在真实的面试中是否遇到过这个题? 是
题目纠错
样例
给出 num = 5 你需要返回 [0,1,1,2,1,2].
挑战
时间复杂度为 O(n * sizeof(integer))的解法很容易想到, 但是你是否可以用线性的时间复杂度 O(n)/可能只遍历一遍吗, 空间复杂度应为 O(n).
你能霸气的完成这项挑战吗? 不借助任何内嵌的函数, 比如C++ 中的__builtin_popcount 亦或是任何其他语言中的方法

解题思路:
bit[n] = bit[n & (n - 1)]+1

class Solution {
public:
    /**
     * @param num: a non negative integer number
     * @return: an array represent the number of 1's in their binary
     */
    vector<int> countBits(int num) {
        // write your code here
        vector<int> vec;
        vec.push_back(0);
        for (int i = 1; i <= num; i++) {
            vec.push_back(vec[i & (i - 1)] + 1);
        }
        return vec;
    }
};
上一篇下一篇

猜你喜欢

热点阅读