如何使用按位运算符、掩码来查找一个数是否是另一个数的倍数？

Question

所以有人告诉我这是可以做到的，而且位运算和掩码可能非常有用，但我一定在它们的工作方式上遗漏了一些东西。

我正在尝试计算一个数字，比如 x，是否是 y 的倍数。如果 x 是 y 的倍数，那么故事的大结局，否则我想增加 x 以达到最接近的大于 x 的 y 倍数（以便所有 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 是 101 的倍数，因为它刚刚被转移）。如果我有数字 16，也就是 10000，它的补码是 01111。我如何使用这个补码来判断一个项目是否是 16 的倍数？也有人可以对上面给出的代码给出数字解释吗？展示这个可以帮助我理解为什么它不起作用。一旦我明白为什么它不起作用，我相信我将能够自己解决问题。

Answer 1

我不确定你为什么会 think 为此使用位操作？他们当然有自己的位置，但事实并非如此。

更好的方法是简单地使用类似的东西：

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.

所以可以用表达式检测十六的倍数：

(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 声明为常量 unsigned long，则上面给出的代码有效，因为传入的 x 也是一个 unsigned long。关键点不是长或常量部分，而是数字是无符号的。这个符号位会导致计算错误，因为数字中的第一个位置表示符号，并且在执行按位运算时符号会变得混乱。

如果我们正在寻找 16 的倍数，那么这是我的代码： const 无符号长 y = 16； //在我的案例中全局声明

然后将一个无符号长整数传递给运行以下代码的函数： if(x&(y-1)){ //如果不是0则y的倍数 x = x&~(y-1) + y; } x 现在将是 16 的最接近倍数的大小。