leetcode 868. 二进制间距

题目

运行效率

题解

lowbit(x) 是x二进制表达式中最低位1所代表的数值。即x & -x就是lowbit函数。
例如
当x=22时二进制表示10110则 22&-22既可以得到二进制数值10。
为啥呢？因为我们计算机中负数采用的补码表示。lowbit很好证明。
那我们枚举相邻两个1，取出他们位数所代表的权值相除得到的结果，再通过log对2取对数就能直接得到相邻两个1之间的间隔位数。
例如x=22 二进制10110

• 第一次取出 last = 10(二进制)
• 第二次取出 now = 100（二进制）
• 两者相除取对数。log2(now / last) 就可以直接得到想间隔的距离。

shuw your code

class Solution {
public:
    int binaryGap(int n) {

        int ans = 0; 
        int last = n & -n;  // 上一个最低位 1 所代表的权值
        n -= last;
        while (n)
        {
            int t = n & -n; // 当前最低位 1 所代表的权值
            ans = max(ans, (int)(log(t/last)/log(2)));
            n -= t;
            last = t;
        }
        return ans;
    }
};