読者です 読者をやめる 読者になる 読者になる

いかなる算術演算子も使わずに加算を実現する

という問題を解く。

答えは、ビット演算子をたくみに使って加算を実現する。 つまり、ビット演算子は算術演算子には含まれないので、使っても良い。

具体的には、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

なお、シフト対象となる左辺値の型のサイズより大きい値でシフトしようとすると、以下のようにMacApple 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

浮動小数点数のビット表現

IEEE 754 - Wikipedia

浮動小数点のビット表現を見てみる。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

https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Float_example.svg/590px-Float_example.svg.png

符号部は、負数で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...となる。