Doubling binary digits

Question

How to double a number of binary digits in an integer? For example, if bin(x)="1001" then bin(y) must be "11000011". Is there any smart and fast algorithm ?

UPDATE: Here is an elegant solution:

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

where X is bin(int_x)[2:]

However, I am interested in a more faster way and for the integers of any size. Maybe an arithmetical transformation should help.

Answer 1

Here's one way that should be reasonably fast: convert your number to a binary string, then reinterpret the result as being in base 4. Now to make sure that all the '1's are doubled properly, multiply the result by 3.

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

Answer 2

(Reference http://graphics.stanford.edu/~seander/bithacks.html#Interleave64bitOps):

If your number is below 256, you may use

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

and if it is below 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

Comparison with other solutions (the function must take an integer and return an integer for fair comparison):

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)

Benchmark source code can be found in http://gist.github.com/417172.