いかなる算術演算子も使わずに加算を実現する
という問題を解く。
答えは、ビット演算子をたくみに使って加算を実現する。 つまり、ビット演算子は算術演算子には含まれないので、使っても良い。
具体的には、XORによって各位の加算を実現し、ANDと左シフト演算子によって繰り上げを実現する。 繰り上げがなくなった時点で（ゼロになった時点で）、計算は終了する。
以下のように、デバッグしながら実行してみる。
#include <stdio.h> #define BITS 32 void bit(int n){ int i; for(i=0;i<BITS;i++) printf("%d", (n >> (BITS-1-i)) & 1); printf("\n"); } int bitplus(int a, int b){ bit(a); bit(b); printf("\n"); if(b==0) return a; return bitplus( a^b, (a&b)<<1 ); } int main(int argc, char* argv[]) { int a = atoi(argv[1]); int b = atoi(argv[2]); bit(a); bit(b); printf("\n"); printf("Ans = %d\n\n", bitplus( a^b, (a&b)<<1 )); return 0; }
$ ./bitplus 3 5 00000000000000000000000000000011 00000000000000000000000000000101 00000000000000000000000000000110 00000000000000000000000000000010 00000000000000000000000000000100 00000000000000000000000000000100 00000000000000000000000000000000 00000000000000000000000000001000 00000000000000000000000000001000 00000000000000000000000000000000 Ans = 8 $ ./bitplus 65535 65536 00000000000000001111111111111111 00000000000000010000000000000000 00000000000000011111111111111111 00000000000000000000000000000000 Ans = 131071 $ ./bitplus 65535 65535 00000000000000001111111111111111 00000000000000001111111111111111 00000000000000000000000000000000 00000000000000011111111111111110 00000000000000011111111111111110 00000000000000000000000000000000 Ans = 131070 $ python Python 3.4.3 (default, Oct 24 2015, 14:51:44) [GCC 4.2.1 Compatible Apple LLVM 6.1.0 (clang-602.0.53)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> int("10101010",2) 170 >>> int("01010101",2) 85 >>> quit() $ ./bitplus 170 85 00000000000000000000000010101010 00000000000000000000000001010101 00000000000000000000000011111111 00000000000000000000000000000000 Ans = 255 $ ./bitplus 171 85 00000000000000000000000010101011 00000000000000000000000001010101 00000000000000000000000011111110 00000000000000000000000000000010 00000000000000000000000011111100 00000000000000000000000000000100 00000000000000000000000011111000 00000000000000000000000000001000 00000000000000000000000011110000 00000000000000000000000000010000 00000000000000000000000011100000 00000000000000000000000000100000 00000000000000000000000011000000 00000000000000000000000001000000 00000000000000000000000010000000 00000000000000000000000010000000 00000000000000000000000000000000 00000000000000000000000100000000 00000000000000000000000100000000 00000000000000000000000000000000 Ans = 256
右シフト演算
負の値を右シフトした場合、符号ビットが立っているので、1で埋められる。
...
int k = -65535;
bit(k);
bit(k>>=10);
bit(k<<=10);
...
11111111111111110000000000000001 11111111111111111111111111000000 11111111111111110000000000000000
なお、シフト対象となる左辺値の型のサイズより大きい値でシフトしようとすると、以下のようにMac（Apple LLVM version 7.0.2 (clang-700.1.81)）ではwarningが出るが実行はできる。
...
bit(k>>=64);
...
$ gcc bitplus.c
bitplus.c:87:14: warning: shift count >= width of type [-Wshift-count-overflow]
bit(k>>=64);
^ ~~
1 warning generated.
ただ、結果としての値は、シフト演算を行う前の値になっていた。
11111111111111110000000000000001
Cではこのようなシフト演算は規定外なので、何が起こるかはプラットフォームに依存する。
Goだと、以下の記事の通り、-1になる。
Goでは、nビットシフトは1ビットシフトをn回行ったのと同じ（CやJavaは違う） - Qiita
$ cat bit.go package main import ( "fmt" ) func main() { var a int32 = -65535 fmt.Printf("%b\n", a>>64) }
$ go run bit.go
-1
浮動小数点数のビット表現
浮動小数点のビット表現を見てみる。float型の変数からアドレスを取得し、それをint型のポインタとしてキャストしてから、その値を取り出す。
#include <stdio.h> #define BITS 32 void bitf(float f){ int i; int n = *((int *)&f); for(i=0;i<BITS;i++) printf("%d", (n >> (BITS-1-i)) & 1); printf("\n"); } int main() { bitf(-10.5); bitf(10.5); return 0; }
$ ./floatbit 11000001001010000000000000000000 01000001001010000000000000000000
符号部は、負数で1、正数で0。 仮数部と指数部の算出は以下の通り。 算出した指数部には規定通り127のバイアスを加える。
10.5 * 2^0 = 5.25 * 2^1 = 2.625 * 2^2 = 1.3125 * 2^3 = (1+0.3125) * 2^3 0.3125 * 2 = 0.625 (0) 0.625 * 2 = 1.25 (1) 0.25 * 2 = 0.5 (0) 0.5 * 2 = 1.0 (1)
指数部は3+127=130で10000010、仮数部は2ビット目と4ビット目が立つので0101、となるので、-10は1_10000010_01010000...となる。
