数学ガールの秘密ノート第104回をRubyとCで実装


格好良い実装: http://qiita.com/cielavenir/items/8622dcd3ef14b2cfa85a

##縁取り

lambdaをmapすることで、フィルタっぽい感じは示せたと思う。
しかし、「宿題」の方は、transposeを使ったので負けだと思っている。

```rb:mathgirl104.rb
#!/usr/bin/ruby

#こういう時にゴルーチンって便利っぽいよねーと感じる…
filter_right=lambda{|m|
	m.map{|e|(e>>1)&0xffff}
}
filter_left=lambda{|m|
	m.map{|e|(e<<1)&0xffff}
}
filter_up=lambda{|m|
	[0]+m[0..14]
}
filter_down=lambda{|m|
	m[1..15]+[0]
}

#Q1
m=DATA.map{|e|e.to_i(2)}
[filter_right,filter_left,filter_up,filter_down].map{|e|
	e.call(m)
}.transpose.map{|e|
	e.reduce(:&)^0xffff
}.zip(m).map{|x,y|
	x&y
}.each{|e|
	puts '%016b'%e
}

#Q2
puts m.map{|e|
	'%016b'%e
}.map{|e|
	e.reverse.each_char.to_a
}.transpose.map{|e|
	e.reverse.join
}

__END__
0000000000000000
0000000000000000
0011111111111100
0011111111111100
0011111111111100
0011100000000000
0011100000000000
0011111111100000
0011111111100000
0011111111100000
0011100000000000
0011100000000000
0011100000000000
0011100000000000
0000000000000000
0000000000000000
```

##反転(ビットスワップ/バイトスワップ)

普通に実務でも使えそうな速いコードだと思います。目からうろこ。ただ、unsignedが使えない言語だとあれだったりするんだろうか。

```c:mathgirls104.c
#include <stdio.h>

unsigned long long bitswap64(unsigned long long n){
	const unsigned long long m1=0x5555555555555555ULL;
	const unsigned long long m2=0x3333333333333333ULL;
	const unsigned long long m4=0x0f0f0f0f0f0f0f0fULL;
	const unsigned long long m8=0x00ff00ff00ff00ffULL;
	const unsigned long long m16=0x0000ffff0000ffffULL;
	const unsigned long long m32=0x00000000ffffffffULL;
	n=((n&m1)<<1)|((n>>1)&m1);
	n=((n&m2)<<2)|((n>>2)&m2);
	n=((n&m4)<<4)|((n>>4)&m4);
	n=((n&m8)<<8)|((n>>8)&m8);
	n=((n&m16)<<16)|((n>>16)&m16);
	n=((n&m32)<<32)|((n>>32)&m32);
	return n;
}
unsigned int bitswap32(unsigned int n){
	const unsigned int m1=0x55555555;
	const unsigned int m2=0x33333333;
	const unsigned int m4=0x0f0f0f0f;
	const unsigned int m8=0x00ff00ff;
	const unsigned int m16=0x0000ffff;
	n=((n&m1)<<1)|((n>>1)&m1);
	n=((n&m2)<<2)|((n>>2)&m2);
	n=((n&m4)<<4)|((n>>4)&m4);
	n=((n&m8)<<8)|((n>>8)&m8);
	n=((n&m16)<<16)|((n>>16)&m16);
	return n;
}
unsigned short bitswap16(unsigned short n){
	const unsigned short m1=0x5555;
	const unsigned short m2=0x3333;
	const unsigned short m4=0x0f0f;
	const unsigned short m8=0x00ff;
	n=((n&m1)<<1)|((n>>1)&m1);
	n=((n&m2)<<2)|((n>>2)&m2);
	n=((n&m4)<<4)|((n>>4)&m4);
	n=((n&m8)<<8)|((n>>8)&m8);
	return n;
}
unsigned char bitswap8(unsigned char n){
	const unsigned char m1=0x55;
	const unsigned char m2=0x33;
	const unsigned char m4=0x0f;
	n=((n&m1)<<1)|((n>>1)&m1);
	n=((n&m2)<<2)|((n>>2)&m2);
	n=((n&m4)<<4)|((n>>4)&m4);
	return n;
}

unsigned long long byteswap64(unsigned long long n){
	const unsigned long long m8=0x00ff00ff00ff00ffULL;
	const unsigned long long m16=0x0000ffff0000ffffULL;
	const unsigned long long m32=0x00000000ffffffffULL;
	n=((n&m8)<<8)|((n>>8)&m8);
	n=((n&m16)<<16)|((n>>16)&m16);
	n=((n&m32)<<32)|((n>>32)&m32);
	return n;
}
unsigned int byteswap32(unsigned int n){
	const unsigned int m8=0x00ff00ff;
	const unsigned int m16=0x0000ffff;
	n=((n&m8)<<8)|((n>>8)&m8);
	n=((n&m16)<<16)|((n>>16)&m16);
	return n;
}
unsigned short byteswap16(unsigned short n){
	const unsigned short m8=0x00ff;
	n=((n&m8)<<8)|((n>>8)&m8);
	return n;
}

unsigned long long popcnt64(unsigned long long n){
	const unsigned long long m1=0x5555555555555555ULL;
	const unsigned long long m2=0x3333333333333333ULL;
	const unsigned long long m4=0x0f0f0f0f0f0f0f0fULL;
	const unsigned long long m8=0x00ff00ff00ff00ffULL;
	const unsigned long long m16=0x0000ffff0000ffffULL;
	const unsigned long long m32=0x00000000ffffffffULL;
	n=((n>>1)&m1)+(n&m1);
	n=((n>>2)&m2)+(n&m2);
	n=((n>>4)&m4)+(n&m4);
	n=((n>>8)&m8)+(n&m8);
	n=((n>>16)&m16)+(n&m16);
	n=((n>>32)&m32)+(n&m32);
	return n;
}
unsigned int popcnt32(unsigned int n){
	const unsigned int m1=0x55555555;
	const unsigned int m2=0x33333333;
	const unsigned int m4=0x0f0f0f0f;
	const unsigned int m8=0x00ff00ff;
	const unsigned int m16=0x0000ffff;
	n=((n>>1)&m1)+(n&m1);
	n=((n>>2)&m2)+(n&m2);
	n=((n>>4)&m4)+(n&m4);
	n=((n>>8)&m8)+(n&m8);
	n=((n>>16)&m16)+(n&m16);
	return n;
}
unsigned short popcnt16(unsigned short n){
	const unsigned short m1=0x5555;
	const unsigned short m2=0x3333;
	const unsigned short m4=0x0f0f;
	const unsigned short m8=0x00ff;
	n=((n>>1)&m1)+(n&m1);
	n=((n>>2)&m2)+(n&m2);
	n=((n>>4)&m4)+(n&m4);
	n=((n>>8)&m8)+(n&m8);
	return n;
}
unsigned char popcnt8(unsigned char n){
	const unsigned char m1=0x55;
	const unsigned char m2=0x33;
	const unsigned char m4=0x0f;
	n=((n>>1)&m1)+(n&m1);
	n=((n>>2)&m2)+(n&m2);
	n=((n>>4)&m4)+(n&m4);
	return n;
}

int main(){
	unsigned long long x=12345678901234567890ULL;
	printf("%llu\n",bitswap64(x));
	printf("%llu\n",byteswap64(x));
	printf("%llu\n",popcnt64(x));
}
```

## popcnt

上のコード、popcntもできるようにしてみた。今までpopcntは黒魔術だと思っていたが、とりあえず何をやっているかだけは理解できるようになった。