2个二进制数的公共位数

Question

我正在编写一个程序来计算给定数字的两个二进制表示之间的共同位数。我写的代码是：

int common_bits(int a, int b) {


static long binaryNo1,binaryNo2,remainder1,remainder2,factor = 1;

if(a!= 0&&b!=0){

     remainder1 = a % 2;
     binaryNo1 = remainder1 * factor;
     remainder2 = b % 2;
     binaryNo2 = remainder2 * factor;
     factor = factor * 10;
     if (binaryNo2==binaryNo1)
     {
         int count=0;
         count++;

     }
    common_bits(a/2,b/2);
}

        return 0;



}

我一直面临着这个错误，任何人都可以解释原因并告诉我如何更正它。

其工作原理的一个示例是：13（二进制为 1101）和 7（二进制为 111）有 2 个共同位

提前致谢。

Answer 1

您不需要构建将二进制数字串视为十进制数字的数值，这几乎是您所有问题的根源。好吧，实际上并不是那个想法导致您问题，但你用来尝试实现这个想法的代码风格很差。 static 变量不好，尤其是递归。未能 return 值也很糟糕。

够了：

int common_bits(int a, int b)
{
    if (a == 0) return 0;
    if (b == 0) return 0;
    return ((a&1) == (b&1)) + common_bits(a/2, b/2);
}

之所以有效，是因为 a&1 获得了 a 的最低位，并且当两个操作数相等时 == 的计算结果为 1，否则为 0。

或者您可以使用 XNOR，有时也称为按位 EQV：

return ((a^~b)&1) + common_bits(a/2, b/2);

Answer 2

首先，让我们修复你的程序：你的代码在递归调用后没有return任何东西，乘以一个不必要的因子，使用因子 10^k 而不是 2^k，并使用了不必要的递归。修复相当简单：

remainder1 = a % 2;
remainder2 = b % 2;
int count = 0;
if (remainder1 == remainder2) {
    count++;
}
return count + common_bits(a/2, b/2);

2个二进制数的公共位数

number of digits common between 2 binary numbers

c

recursion

binary