1バイト中の0-7ビットの内容を7-0ビットに反転させるメソッド

標題を実現するメソッドを考えていたが、ちょっと面倒だと思った。
ググると素晴らしいメソッドを発見した。

上記はパッと見何をやっているかわからなかった。
だが2進数で見ると動きが理解できたので8ビット版を作ることができた。

  function rev(x){
    x = x & 0xff;// 8bit整数
    x = ((x & 0x55) << 1) | ((x >>> 1) & 0x55);
    x = ((x & 0x33) << 2) | ((x >>> 2) & 0x33);
    x = ((x & 0x0F) << 4) | ((x >>> 4) & 0x0F);
    return x;
  }

まず最初のこれ。

    x = ((x & 0x55) << 1) | ((x >>> 1) & 0x55);

xには10100101(0xa5)の値が入っているとする。
これは以下のような動きをする。まず最初のx & 0x55。これはxの値と2進数の01010101(0x55)とのビット単位でのand演算を行う。なので、

    x ... 10100101 
      and
0x55  ... 01010101 
      =   00000101

次にこの値を左に1つシフトする。

00000101 << 1 => 00001010 ... (1)

になる。

次に x >>> 1だが、これはxの値を1つ右にシフトする演算である。

x >>> 1 => 10100101 >>> 1 => 01010010

でこの値とand演算をする。

         01010010
         and
0x55 ... 01010101 
      =  01010000 ... (2)

となる。そして(1)と(2)の値のor演算を行う。

         00001010 ... (1)
         or
         01010000 ... (2)
       = 01011010 ... (3)

となる。最初の値と(3)の値を比べると、2ビットごとに各ビットが入れ替わっていることがわかる。
続いて2ビットのペア、4ビットのペアでも行うことで8ビットのビット反転が完成する。

  function rev(x){
    x = x & 0xff;
    // (a) 0bitと1bit、2bitと3bit、4bitと5bit、6bitと7ビットの入れ替え
    x = ((x & 0x55) << 1) | ((x >>> 1) & 0x55);
    // (b) 0-1bitと2-3bit、4-5bitと6-7bitの入れ替え
    x = ((x & 0x33) << 2) | ((x >>> 2) & 0x33);
    // (c) 0-3bit、4-7bitの入れ替え
    x = ((x & 0x0F) << 4) | ((x >>> 4) & 0x0F);
    return x;
  }

ソース中の(a),(b),(c)のビット単位での動きは、xの値が10000100(0x84)の場合は以下のとおりである。
見事に反転している。

bit 7   6     5   4     3   2     1   0
---------------------------------------------
(a) 1<->0  |  0<->0  |  0<->1  |  0<->0  2ビットごとに区切り各ビットを入れ替え
    0   1     0   0     1   0     0   0
(b)(0   1)<->(0   0) | (1   0)<->(0   0) 4ビットを2ビットのペアで区切り、ペアを入れ替え
    0   0     0   1     0   0     1   0 
(c)(0   0     0   1)<->(0   0     1   0) 8ビットを4ビットのペアで区切り、ペアを入れ替え
    0   0     1   0     0   0     0    1

理屈としてはわかったけど、最初にこれを考えた人はすごいなと思った。