9

我最近在一次采访中被问到，只使用位移运算符，编写一些代码来告诉你一个数字是否可以被 8 整除，显然代码很短 - 有人知道吗？

注意：如果您不需要使用移位，您可以使用n类似的掩码测试低位是否为全零x&7 == 0，或者更一般地说 x & ((1UL << n) - 1) == 0。 如何仅使用逻辑运算符 AND 判断一个数字是否是四的倍数？

4

9 回答 9

25

对于以二进制表示的任何整数，除以任何 2 的幂的余数只是低位的值，因此0b11001110除以0b1000有余数0b110。因此，为了检查是否可被 8 整除，您需要检查三个低位是否全为零：

if (((x >> 3) << 3) == x)
  divisibleBy8 = true;

右移清除底部三位，然后左移恢复幅度，然后与原始数字进行比较。

正如其他人指出的那样，如果您知道整数的位宽，您可以这样做

if (!(x<<29))
  divisibleby8 = true;

对于 64 位整数等，将 29 替换为 61。显然在 Java 中你可以这样做：

if ((x << -3) != 0)
  divisibleby8 = true;

因为负移位如-3被解释为bit_width - 3，它适用于 32 位和 64 位整数。

（你不需要所有的括号，为了清楚起见，我已经包括在内）

只是为了完整性

这些都是测试被 8 整除的非常糟糕的方法。做起来if !(x & 7)更清晰，几乎可以肯定一样快或更快。

于 2013-06-24T18:16:07.347 回答
9 
int num;

if(!(num & 7)) {
     // num divisible by 8
}

或者

if(! (num << 29) ) { // assuming num is 32 bits
    // num divisible by 8
}
于 2013-06-24T18:16:43.007 回答
4

在 Java 中，不知道类型是否是long或者int你可以做到这一点

if((x << -3) != 0)

这将根据该类型移动 29 或 61 位。只有低三位为 0 时才成立。

于 2013-06-24T18:20:16.637 回答
2 
if (x & ((1 << 3)-1) == 0)

或者，如果您真的想使用移位：

if (x == ((x >> 3) << 3))
于 2013-06-24T18:18:37.260 回答
1

检查 n 是否能被 9 整除的最简单方法是执行 n%9。另一种方法是将 n 的数字相加。如果数字之和是 9 的倍数，则 n 是 9 的倍数。上述方法不是基于位运算符的方法，需要使用“%”和“/”。按位运算符通常比模和除法运算符快。以下是一种基于位运算符的方法，用于检查被 9 的整除性。

你应该检查这个链接 http://www.firmcodes.com/check-number-multiple-9-using-bitwise-operators/

于 2015-01-12T06:19:59.340 回答
0

x << (32-3) == 0对于一个int；x << (64-3) == 0L对于一个long。

于 2013-06-24T18:28:08.153 回答
0

为了简单起见

如果你想知道任何给定的整数 N 是否是 X 的倍数，是 X 的 2 的幂，只需执行以下操作：

    public static boolean isMultipleOfpowerOf2(int n, int x) {
    if((n&(x-1))==0){
       return true;
    }else {
        return false;
    }
}

为什么这个工作？

考虑 X = 8；

8:        1000*
9:        1001
10:       1010
11:       1011
12:       1100
13:       1101
14:       1110
15:       1111***
16:      10000*
17:      10001
18:      10010
19:      10011
20:      10100
21:      10101
22:      10110
23:      10111***
24:      11000*

现在您可以清楚地看到，8 的任何倍数都不使用 3* 右位，这适用于 2 的所有幂。您可以看到 X-1、7 使用所有这些位***。

现在剩下的很简单，您可以使用 &(X-1) 屏蔽所有其他位，如果答案为零，则您有一个倍数。

N & (X-1) with  N = 9, X=8

N(9)    = 1001
X(8-1)  = 0111
N&(X-1) = 0001  this case is != 0

N(16)   = 10000
X(8-1)  = 00111
N&(X-1) = 00000  this time is == 0, it is a multiple.

可以在这篇非常好的文章中找到更多信息： 使用位运算符来处理颜色

于 2015-05-17T00:49:10.410 回答
0 
if (((x >> 3) << 3) == x)
    divisibleBy8 = true;

对于输入 0（零），这将失败

于 2017-05-23T18:08:47.167 回答
-4 
static boolean divisibleBy8(int num) {
    return (number & 7) == 0;
}
于 2013-06-24T18:15:56.927 回答