XOR ビット 交換 逆順 表 C言語 C/C++ FFT

nビット数のビット逆順表を作るアルゴリズムを理解するには、0ビットから桁数を増やしながら正順と逆順の対応表を作成する流れを想定してみるとよい。

kビットまでの表がある状態から、1ビット桁数を増やして表を拡張する過程を考える。
正順のほうは、元々の(k)ビット列に対し、(k+1)ビット目に1が加わったビット列が、追加されることになる。
逆順のほうは、元々の(k)ビット列に対し、(n-k)ビット目に1が加わったビット列が、追加されることになる。
これを繰り返すと、ビット逆順表が出来上がる。加算のみでビット演算はしていない。
数値例は下記のサイトが分かりやすい。
鳥の巣箱：ビット反転アルゴリズム

上記の過程を繰り返すと、正順の偶数(2*j)のビット反転をrev(2*j)とすれば、
正順の偶数とそれに1を加えた奇数の全てに対し、下記が成り立っていることがわかる。
rev(2*j) = rev(2*j)
rev(2*j+1) = rev(2*j) + 2^(n-1)
さらに、正順の値を中央で分けると、
rev(2*j + 2^(n-1)) = (rev(2*j)) + 1
rev(2*j + 2^(n-1)+1) = (rev(2*j) + 2^(n-1)) + 1
となり、0...0、0...1、1...0、1...1のビット逆順は同時に求められることになるので、ビット逆順を求める呼出が4分の1で済む。0から2ずつ加算しながら0...0のビット逆順を求めれば、1...0と1...1のビット逆順は計算で求まり、0...1のビット逆順は1...0の対称のビット逆順に結果的に含まれる。
C言語のソースコードを含め下記のサイトで紹介されている。
Ooura's Mathematical Software Packages：FFT (高速フーリエ・コサイン・サイン変換) の概略と設計法

XOR演算は、繰り上げを含む加算の処理に近い。1をビットシフトしながら繰り上げがなくなるまでXOR演算を行えば、繰り上げ処理を含む1の加算を下位ビットから上位ビットに向かって1ビットずつ行ったことになる。繰り上げがある桁は1から0に変わるので、繰り上げがあるうちはXOR演算後がXOR演算前よりも下回ることになり、それがなくなれば計算終了ということになる。これを通常とは逆に、上位ビットから下位ビットに向かってのXOR演算を行えば、ビット逆順を逐次求めることができる。ビット逆順を求める場合には、XOR演算後がXOR演算前よりも下回らなくなるという終了判定の他に、ビットシフト値よりも下回らなくなる（上位ビット側で繰り上げが終了し＝上位ビット側がすべて0になり、ビットシフト値以上となった）という終了判定もできる。

XOR ビット 交換 逆順 ビッグエンディアン リトルエンディアン マスク セット 反転

C言語でのビット演算子を整理。

bit1 & bit2：AND演算
bit1 | bit2：OR演算
bit1 ^ bit2：XOR演算(0^0→0,0^1→1,1^0→1,1^1→0)
~bit：NOT演算

特定ビットを0にすることをマスクといいAND演算が用いられ、特定ビットを1にすることをセットといいOR演算が用いられる。特定ビットを反転させるにはXOR演算が用いるが、マスクするビットは元の値＋マスクしないビットは0としてマスクをXOR演算で行うこともできる。

XORは剰余算に相当し、bit1÷bit2の余りが求まる。剰余算をしない桁はbit1とbit2の0か1を一致させておく。
ビット演算の際はchar型もint型に変換されて行われる。処理系に依存する／しないはよくわからないが、変換後のint型の上位ビットと変換前のchar型の上位ビットが一致する（符号が維持される）場合がある。

XOR演算 x ^ y の結果は、x と y をビット単位で比較して、反転していない桁には0、反転している桁には1、が入る結果となる。

XORは値同士の交換に利用できる。例えば下記のようになる。
t = (x ^ y) & 0xf; //下位4bit分で、bit値が反転するbitに1が入る。
x ^= t： //下位4bit分で、必要な位置だけbit値が反転することでyに置き換わる

XORは値のbit交換にも利用できる。例えば下記のようになる。
t = (x ^ (x >> 4)) & 0xf; //下位4bit分で、bit値が反転する位置に1が入る。
t |= t << 4; //上位4bit分も、bit値が反転する位置（＝下位4bit分と同じ位置）に1が入る。
x ^= t; //必要な位置だけbit値が反転することでbit交換される。

ビット演算を上手く利用すると、ビッグエンディアン、リトルエンディアンに非依存の処理を行うことができる。