查找数字是否可被8整除-使用移位运算符 [英] find if a number is divisible by 8 - using bit shifting operators

问题描述

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

I was recently asked during an interview, using just bit shift operators, write some code that would tell you if a number is divisible by 8, apparently the code is very short - does anyone have a clue?

注意:如果不需要使用移位，则可以使用x&7 == 0之类的掩码来测试n的低位是否为全零，或更普遍的是 x & ((1UL << n) - 1) == 0.

Note: if you aren't required to use shifts, you'd test the low n bits for being all-zero with a mask like x&7 == 0, or more generally x & ((1UL << n) - 1) == 0. How can I tell if a number is a multiple of four using only the logic operator AND?

推荐答案

对于任何以二进制表示的整数，除以2的任意幂的余数就是低阶位的值，因此0b11001110除以有余数0b110.因此，为了检查除数是否为8，您需要检查三个低阶位是否全部为零:

With any integer represented in binary the remainder of division by any power of two is simply the value of the bits of lower order so 0b11001110 divided by 0b1000 has remainder 0b110. So in order to check for divisibility by 8 you need to check if the three low order bits are all zero:

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

右移会清除左三位，然后左移将恢复幅度，然后与原始数字进行比较.

Right shifting clears the bottom three bits before the left shift restores the magnitude and then compare to the original number.

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

As others have pointed out, if you know the bit width of the integer you can do this

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

用64位整数等将29乘61代替.显然，在Java中，您可以执行以下操作:

Replace that 29 by 61 for 64-bit integers, etc. Apparently in Java you can do this:

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

由于负移位(例如-3)被解释为bit_width - 3，因此它可以同时用于32位和64位整数.

Because negative shifts such as -3 are interpreted as bit_width - 3 and it will work with both 32- and 64-bit integers.

(您不需要所有括号，为清楚起见，我已将其包括在内)

(You don't need all the brackets, I've included for clarity)

仅出于完整性考虑

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

These are all pretty bad ways to test for divisibility by 8. Doing if !(x & 7) is clearer and almost certainly as fast or faster.

这篇关于查找数字是否可被8整除-使用移位运算符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！