c-如何使用位运算符掩码来确定一个数字是否是另一个数字的倍数

Question

所以我被告知这是可以做到的，逐位操作和掩码可能非常有用，但我一定在它们的工作方式上遗漏了一些东西。

我试图计算一个数字，比如x，是否是y的倍数。如果x是y的乘积，那么故事就结束了，否则我想增加x，达到y的最接近倍数，即大于x（这样所有x都符合结果）。我刚开始学习C，很难理解其中的一些任务。

这是我尝试过的，但当我输入5、9或24等数字时，我会分别得到以下结果：0、4、4。

    if(x&(y-1)){ //if not 0 then multiple of y
        x = x&~(y-1) + y;
    }

任何解释，幕后发生的数学例子，都将不胜感激。

编辑：所以为了澄清，我在一定程度上理解了一个项目是否是倍数的比特移位。（正如在回复10100中所解释的，10100是101的倍数，因为它刚刚被移位）。如果我有数字16，它是10000，它的补码是01111。我该如何使用这个补码来判断一个项目是否是16的倍数？还有人能对上面给出的代码给出一个数字解释吗？展示这一点可以帮助我理解为什么它不起作用。一旦我明白为什么它不起作用，我相信我就能自己解决问题。

Answer 1

我不知道你为什么要考虑对此使用位操作？他们当然有自己的位置，但事实并非如此。

一个更好的方法是简单地使用这样的东西：

unsigned multGreaterOrEqual(unsigned x, unsigned y) {
    if ((x % y) == 0)
        return x;
    return (x / y + 1) * y;
}

---

但是，要回答您添加的问题，即如果一个数字是十六的倍数，您将如何计算，这可以相对容易地完成。你会注意到下面所有倍数的模式：

  0 == 0000 0000 0000 0000
 16 == 0000 0000 0001 0000
 32 == 0000 0000 0010 0000
 48 == 0000 0000 0011 0000
 64 == 0000 0000 0100 0000
 :
512 == 0000 0010 0000 0000
                      __/
                       
                        These bits are always zero.

因此，可以用以下表达式检测到16的倍数：

(value & 0x0f) == 0

然而，这只适用于二次幂，而不适用于任意除数。

Answer 2

在琐碎的情况下，每个2次幂的偶数倍的数字都会向左移动（这在可能更改符号位时不适用）

例如

10100

是的4倍

101

以及10100

是2倍

1010

至于其他倍数，则必须通过组合两次移位的输出来找到。你可能想查找一些原始的计算机划分方法，其中的划分看起来大致像

x = a / b

像一样实现

buffer = a
while a is bigger than b; do
  yes: subtract a from b
       add 1 to x
done

更快的例程尝试先计算出更高级别的位置值，跳过很多减法。所有这些例程都可以按位执行；但这是一个巨大的痛苦。在ALU中，这些例程是按位执行的。可能想查阅一本数字逻辑设计书，了解更多想法。

Answer 3

好的，所以我已经发现了代码中的错误，因为大多数人说使用掩码无法计算一个数字是否是另一个数字的倍数，我想我会分享我所学到的。这是可能的！-如果您使用的是正确的数据类型，即.

如果y被声明为常量无符号长，则上面给出的代码有效，因为传入的x也是无符号长。关键点不是长或常数部分，而是数字是无符号的。这个符号位会导致错误计算，因为数字的第一位表示符号，并且在执行逐位操作时，符号可能会混淆。

如果我们要寻找16的倍数，下面是我的代码：const无符号长y=16//在我的案例中是全球申报的

然后将一个无符号的long传递给运行以下代码的函数：如果（x&（y-1））｛//如果不是0，则y的倍数x＝x&（y-1）+y；}x现在将是16的最接近倍数的大小。