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交換される。

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

プラレール 京急 新1000形

プラレールで 京急新1000形 は以下の商品に含まれている。

●京急新1000形 → 1001編成、快特羽田空港行

●京急新1000形ステンレス車 → 1121編成、エアポート急行羽田空港行

●京急新1000形 KEIKYU YELLOW HAPPY TRAIN → 1057編成、特急三崎口行
・2014年12月22日発売（2014年12月20日先行発売）
※プラキッズ京急運転士（数量限定）付
・京急電鉄：2015年12月11日発売（※再生産）

●京急新1000形 → 1025編成、エアポート急行新逗子行
・2015年04月08日発売
※プラキッズ京急運転士（数量限定）付

●京急新1000形ダブルセット
○京急新1000形
○京急新1000形 KEIKYU YELLOW HAPPY TRAIN

●京急トリプルセット
○京急新1000形 KEIKYU YELLOW HAPPY TRAIN
・京急電鉄：2016年05月29日発売

●京急新1000形ダブルセット
○京急新1000形ステンレス車
○京急新1000形1800番台
・京急ステーションコマース：2017年06月10日発売（2017年05月28日先行発売）
→おとどけいきゅう（絶版）

●京急新1000形マイナーチェンジ車 → 1601編成、普通浦賀行
・京急電鉄：2017年08月25日発売（2017年08月18日先行発売）
→おとどけいきゅう
※プラキッズ京急女性車掌（数量限定）付

●京急新1000形1800番台 → 1805編成、特急品川行
・京急電鉄、京急ステーションコマース：2017年10月06日発売（2017年09月29日先行発売）
→おとどけいきゅう

●京急新1000形 KEIKYU YELLOW HAPPY TRAIN → 1057編成、エアポート快特羽田空港行
・京急電鉄：2017年12月22日発売（2017年12月15日先行発売）
→おとどけいきゅう（絶版）

●京急新1000形 リラックマトレイン
・京急電鉄：2018年01月12日発売（2018年01月05日先行発売）
→おとどけいきゅう

●京急リラックマトレイントリプルセット
○新1000形 KEIKYU TRAD TRAIN「リラックマのイチゴお祝い号」
○新1000形 KEIKYU YELLOW HAPPY TRAIN「しあわせのキイロイトリ号」
・京急電鉄：2018年04月07日発売（2018年04月01日先行発売）
→おとどけいきゅう（絶版）

●新1000形 KEIKYU YELLOW HAPPY TRAIN「しあわせのキイロイトリ号」
・京急電鉄：2018年04月27日発売
→おとどけいきゅう

●新1000形 KEIKYU TRAD TRAIN「リラックマのイチゴお祝い号」
・京急電鉄：2018年04月27日発売
→おとどけいきゅう

●京急新1000形 KEIKYU TRAD TRAIN すみっコぐらし号
・京急電鉄：2019年12月21日発売
→おとどけいきゅう

●京急新1000形 KEIKYU YELLOW HAPPY TRAIN → 1057編成、エアポート急行逗子・葉山行
・京急電鉄：2020年09月11日発売

●サウンドプラレール 京急新1000形（アルミ車）
・京急電鉄：2021年07月10日発売