美文网首页
n & (n - 1) 抹去最后一个1

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

作者: Magic11 | 来源:发表于2019-01-25 08:55 被阅读0次

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

    相关文章

      网友评论

          本文标题:n & (n - 1) 抹去最后一个1

          本文链接:https://www.haomeiwen.com/subject/ufrujqtx.html