找到一个数字是否可被8整除 - 使用位移算子

Question

我最近在一次采访中被问到,只使用位移操作符,编写一些代码,告诉你一个数字是否可被8整除,显然代码很短 - 有没有人有线索？

Answer 1

对于以二进制表示的任何整数,除以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)更清楚,几乎肯定是快速或更快.

Answer 2

int num;

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

要么

if(! (num << 29) ) { // assuming num is 32 bits
    // num divisible by 8
}