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

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

縁取り

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

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が使えない言語だとあれだったりするんだろうか。

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は黒魔術だと思っていたが、とりあえず何をやっているかだけは理解できるようになった。