[交流] Euler 工程 第三十六题： 已有3人参与

#include
#include

static const int deBruijn[32] =
{
    0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,  \
    8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31   \
}; //二元五阶deBruijn序列B(2,5)：长度为5的子序列在整个序列中循环唯一

int main(){
    unsigned int i;
    uint32_t v, t;
    int bits;
    int digits;

    for(i=0; i<1000000; i++){
        //判定十进制回文
        v = i;
        t = 0;
        while(v){
            t = t*10 + v%10;
            v /= 10;
        }
        if(t!=i) continue; //若十进制不是回文跳回

        //计算二进制位数
        v = i | (i>>1);
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16; //把最高位的1右边全部置为0

        bits = deBruijn[(v * 0x07C4ACDDU) >> 27] + 1; //获得二进制表示的i值的位数，0x07C4ACDD是一个32bit的deBruijn序列

        //反转无符号整型i的二进制形式，并移动到和原来位数对齐的形式
        v = ((i>>1) & 0x55555555) | ((i & 0x55555555) << 1);
        v = ((v>>2) & 0x33333333) | ((v & 0x33333333) << 2);
        v = ((v>>4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
        v = ((v>>8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
        v = ((v>>16) | (v<<16)) >> (32-bits);

        //若二进制为回文则输出
        if(i==v){
            printf("%d\n", i);
        }
    }

    return 0;
}

0
1
3
5
7
9
33
99
313
585
717
7447
9009
15351
32223
39993
53235
53835
73737
585585

Process returned 0 (0x0)   execution time : 0.031 s
Press any key to continue.

# Project Euler Problem 36
#

def checkBinaryReverse(n):
    s = bin(n)[2:]
    r = s[::-1]
    if r == s:
        return True
    return False

# 2-, 3-, 4-digits
for x in xrange(1, 10, 2):
    # 2-digits
    n = int("%d"*2 % (x, x))
    if checkBinaryReverse(n):
        print n, "=>", bin(n)[2:]

    # 3-, 4-digits
    for y in xrange(1, 10):
        # 3-digits
        n = int("%d"*3 % (x, y, x))
        if checkBinaryReverse(n):
            print n, "=>", bin(n)[2:]
        # 4-digits
        n = int("%d"*4 % (x, y, y, x))
        if checkBinaryReverse(n):
            print n, "=>", bin(n)[2:]

        # 5-, 6-digits
        for z in xrange(1, 10):
            # 5-digits
            n = int("%d"*5 % (x, y, z, y, x))
            if checkBinaryReverse(n):
                print n, "=>", bin(n)[2:]
            # 6-digits
            n = int("%d"*6 % (x, y, z, z, y, x))
            if checkBinaryReverse(n):
                print n, "=>", bin(n)[2:]

15351 => 11101111110111
33 => 100001
313 => 100111001
32223 => 111110111011111
39993 => 1001110000111001
53235 => 1100111111110011
53835 => 1101001001001011
585 => 1001001001
585585 => 10001110111101110001
717 => 1011001101
73737 => 10010000000001001
7447 => 1110100010111
99 => 1100011

IDLE 2.6.6      
>>> print sum([_x for _x in xrange(1,1000001) if str(_x)==str(_x)[::-1] and str(bin(_x))[2:]==str(bin(_x))[2:][::-1]])
872187
>>>

# Project Euler Problem 36
#

def checkBinaryReverse(n):
    s = bin(n)[2:]
    r = s[::-1]
    if r == s:
        return True
    return False

# odd digits
for x in xrange(1, 1000):
    n = int(str(x)+str(x)[::-1])
    if checkBinaryReverse(n):
        print n, "=>", bin(n)[2:]

# even digits
for x in xrange(1, 100):
    for y in xrange(10):
        n = int(str(x)+str(y)+str(x)[::-1])
        if checkBinaryReverse(n):
            print n, "=>", bin(n)[2:]