JavaScript位运算求助：HackerRank位与题目最优解解析

给定整数N和K（满足2 ≤ K ≤ N），需找出满足0 ≤ A < B ≤ N且(A & B) < K的A & B（按位与）的最大值。

我编写了暴力遍历的代码，可通过可见测试用例，但无法通过隐藏测试用例。

暴力代码：

function bitwiseAnd(N, K) {
    // Write your code here
    let arr = []
    N = parseInt(N,10)
    K = parseInt(K,10)
    for(let a=1; a<N; a++){
        for(let b=a+1; b<=N ; b++){
            if(K>=0 && parseInt(a&b,10) < K && parseInt(a&b,10)>=0) arr.push(parseInt(a&b,10))
            
        }
    }
    return Math.max(...arr)
}

之后我找到了一个可通过所有测试用例的最优解代码，但由于不熟悉位运算（如|、~等），无法理解其原理。

最优解代码：

function bitwiseAnd(N, K) {
    // Write your code here
        var n = parseInt(N);
        var k = parseInt(K);
        var a = k - 1;
        var b = (~a) & -(~a);
        if ( (a | b) > n )
            return(a - 1);
        else
            return(a);
}

请求解析这些位运算操作的含义及该最优解法的实现逻辑。

先明确代码中用到的位运算含义：

• ~x：按位取反，将x的二进制每一位0变1、1变0；在JavaScript中，由于是有符号32位整数，取反结果等价于-x - 1
• x & y：按位与，二进制每一位仅当两个操作数对应位都为1时，结果位才为1，否则为0
• x | y：按位或，二进制每一位只要有一个操作数对应位为1，结果位就为1
• -x：取负数，遵循二进制补码规则，等价于对x按位取反后加1

我们的核心目标是找到小于K的最大A&B值，理论上最理想的候选值就是K-1——只要能找到两个数A<B≤N，使得它们的按位与等于K-1，这就是答案；如果找不到，再退而求其次。

1. 初始化候选值
   var a = k - 1：直接把K-1作为目标候选，因为这是小于K的最大整数，能找到符合条件的A、B的话，这就是最终答案。

2. 提取关键位权
   var b = (~a) & -(~a)：

   • 先计算~a：对K-1取反，得到的二进制中，K-1原本为0的位变为1，为1的位变为0
   • 再计算-(~a)：对~a取负数，根据补码规则，最终结果的二进制中只有~a最右侧的1会保留，其余位都是0——这一步的作用是提取a的二进制里最右侧的0对应的位权（比如a=3即011，最右侧的0在第3位，位权是4）

3. 判断候选值是否可达
   if ( (a | b) > n )：

   • a | b的作用是把a最右侧的0改成1，得到的数等于a + b（因为b是该位的位权）
   • 如果a | b ≤ N，说明存在A=a、B=a|b（满足B≤N），此时A & B = a & (a|b) = a，完全符合条件，直接返回a即可
   • 如果a | b > N，说明找不到这样的B（比a大的数里，和a按位与等于a的最小数就是a|b，但它超过了N），只能退一步返回a-1——此时a-1必然小于K，且一定存在两个数的按位与等于它（比如N和N-1的按位与通常就是这个值）

例子验证 #

• 示例1：N=5，K=3。a=2（二进制10），b=1，a|b=3≤5，返回2。实际存在A=2、B=3，2&3=2<3，是符合条件的最大值。
• 示例2：N=2，K=2。a=1（二进制01），b=2，a|b=3>2，返回0。实际存在A=0、B=1，0&1=0<2，是符合条件的最大值。

内容的提问来源于stack exchange，提问作者Burham B. Soliman