Удвоение двоичных цифр

Question

Как удвоить количество двоичных цифр в целом числе? Например, если bin (x) = "1001", то bin (y) должно быть "11000011". Есть ли какой-нибудь умный и быстрый алгоритм?

ОБНОВЛЕНИЕ: Вот элегантное решение:

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

где X - это bin (int_x) [2:]

Однако меня интересует более быстрый способ и целые числа любого размера. Может быть, арифметическое преобразование должно помочь.

Answer 1

Вот один способ, который должен быть достаточно быстрым: преобразовать ваше число в двоичную строку, а затем переосмыслить результат как находящийся в базе 4. Теперь, чтобы убедиться, что все цифры 1 удвоены, умножьте результат на 3.

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

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 # /1665936/udvoenie-dvoichnyh-tsifr#1665956
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

Простое решение, использующее целочисленную арифметику:

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

Answer 4

any_number - int

str (n) - создает строку из int.

str :: replace (pattern, replace_value) - заменяет все шаблоны в строке на replace_value.

int (str) - делает int из строки.

n=any_number
result_number = int(str(n).replace("0","00").replace("1","11"))

Answer 5

$ python2.6
Python 2.6.5 (r265:79063, Mar 25 2010, 14:13:28)
>>> def dd(n): return eval("0b" + "".join(d * 2 for d in str(bin(n))[2:]))
...
>>> dd(9)
195

Answer 6

def doubledigits(x):
    from math import log
    print (bin(x))
    numdigits = x.bit_length()
    result = 1 << (numdigits*2)
    for i in range(numdigits, -1, -1):
        mask = 1 << i
        if (x & mask > 0):
            rmask = 0b11 << (2*i)
            result = result | rmask
    return result

должен это сделать.

Answer 7

y = 0;
for(i = 15; i  >= 0; i--) {
    if((1 << i) & x) {
       y |= 3;
    }
    y <<= 2;
}