二进制位数翻倍

Question

如何将一个整数的二进制位数翻倍？比如，如果 bin(x) 是 "1001"，那么 bin(y) 就应该是 "11000011"。有没有什么聪明又快速的方法呢？

更新：这里有一个优雅的解决方案：

''.join([''.join(i) for i in zip(X,X)])

其中 X 是 bin(int_x)[2:]

不过，我想要一个更快的方法，适用于任何大小的整数。也许可以通过某种数学变换来实现。

Answer 1

直接使用整数运算的简单解决方案是：

def doubledigits(n):
    result = 0
    power = 1
    while n > 0:
        if n%2==1:
            result += 3*power
        power *= 4
        n //= 2
    return result

Answer 2

(参考链接 http://graphics.stanford.edu/~seander/bithacks.html#Interleave64bitOps):

如果你的数字小于256，你可以使用

@magic
def double_digits_holger8(x):
    m = (x * 0x0101010101010101 & 0x8040201008040201) * 0x0102040810204081
    return ((m >> 49) & 0x5555) | ((m >> 48) & 0xAAAA)

如果它小于65536，

@more_magic
def double_digits_binmag16(x):
    x = (x | x << 8) & 0x00FF00FF
    x = (x | x << 4) & 0x0F0F0F0F
    x = (x | x << 2) & 0x33333333
    x = (x | x << 1) & 0x55555555
    return x | x << 1

与其他解决方案的比较（这个函数必须接受一个整数并返回一个整数，才能进行公平比较）：

Method        Time per 256 calls
--------------------------------
Do nothing        46.2 usec 
Holger8          256   usec
BinMag16         360   usec
Mark             367   usec # http://stackoverflow.com/questions/2928886/doubling-binary-digits/2929198#2929198
Max              720   usec # http://stackoverflow.com/questions/2928886/doubling-binary-digits/2928938#2928938
Peter          1.08    msec # http://stackoverflow.com/questions/2928886/doubling-binary-digits/2928973#2928973
Phiµµ w/o Log  1.11    msec # http://stackoverflow.com/questions/2928886/doubling-binary-digits/2929106#2929106
Jim16          1.26    msec # http://stackoverflow.com/questions/2928886/doubling-binary-digits/2929038#2929038
Elegant        1.66    msec # int(''.join([''.join(i) for i in zip(X,X)]),2)
More Elegant   2.05    msec # int(''.join(chain(*zip(X, X))), 2)

基准测试的源代码可以在 http://gist.github.com/417172 找到。

Answer 3

这里有一种比较快的方法：把你的数字转换成二进制字符串，然后把这个结果当作是四进制来理解。接下来，为了确保所有的'1'都被正确地加倍，可以把结果乘以3。

>>> x = 9
>>> bin(x)
'0b1001'
>>> y = int(bin(x)[2:], 4)*3
>>> bin(y)
'0b11000011'