9

最近のインタビューで、ビット シフト演算子だけを使用して、数値が 8 で割り切れるかどうかを示すコードを作成するように求められました。コードは非常に短いようです。手がかりはありますか?

注: シフトを使用する必要がない場合は、 、またはより一般的には nのようなマスクを使用して、下位ビットがすべてゼロであることをテストします。 論理演算子 AND のみを使用して、数値が 4 の倍数であるかどうかを確認するにはどうすればよいですか?x&7 == 0x & ((1UL << n) - 1) == 0

4

9 に答える 9

25

バイナリで表された任意の整数では、任意の 2 のべき乗による除算の剰余は、単純に下位のビットの値であり、0b11001110除算された0b1000剰余があり0b110ます。したがって、8 で割り切れるかどうかを確認するには、下位 3 ビットがすべてゼロかどうかを確認する必要があります。

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

右シフトは、左シフトが大きさを復元する前に下位 3 ビットをクリアし、元の数値と比較します。

他の人が指摘したように、整数のビット幅を知っていれば、これを行うことができます

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

その 29 を 64 ビット整数などの 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

longJavaでは、タイプがそうであるかどうか、またはintこのトリックを実行できるかどうかを知らなくても

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

これは、そのタイプに応じて 29 ビットまたは 61 ビットシフトされます。下位 3 ビットが 0 の場合にのみ true になります。

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

または、本当にシフトを使用したい場合:

if (x == ((x >> 3) << 3))
于 2013-06-24T18:18:37.260 に答える
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) を使用して他のすべてのビットをマスクするだけです。答えがゼロの場合は倍数になります。

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.

詳細については、次の非常に優れた記事を参照してください: Using Bitwise Operators to Work With Colors

于 2015-05-17T00:49:10.410 に答える
-4 
static boolean divisibleBy8(int num) {
    return (number & 7) == 0;
}
于 2013-06-24T18:15:56.927 に答える