Удвоение двоичных единиц информации
Как удвоить многие двоичные единицы информации в целом числе? Например, если мусорное ведро (x) = "1001" затем мусорное ведро (y) должно быть "11000011". Есть ли какой-либо умный и алгоритм FAST?
ОБНОВЛЕНИЕ: Вот изящное решение:
''.join([''.join(i) for i in zip(X,X)])
где X мусорное ведро (int_x) [2:]
Однако мне интересно более более быстрым способом и для целых чисел любого размера. Возможно, арифметическое преобразование должно помочь.
7 ответов
Вот один способ, который должен быть достаточно быстрым: преобразовать ваше число в двоичную строку, а затем заново интерпретировать результат как основание 4. Теперь, чтобы убедиться, что все '1' удвоены должным образом, умножьте результат на 3.
>>> x = 9
>>> bin(x)
'0b1001'
>>> y = int(bin(x)[2:], 4)*3
>>> bin(y)
'0b11000011'
any_number - int
str (n) - производит строку из int.
str :: replace (шаблон, replace_value) - заменяет все шаблоны в строке на replace_value.
int (str) - делает int из строки.
n=any_number
result_number = int(str(n).replace("0","00").replace("1","11"))
Простое решение с использованием целочисленной арифметики:
def doubledigits(n):
result = 0
power = 1
while n > 0:
if n%2==1:
result += 3*power
power *= 4
n //= 2
return result
(Reference 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.
$ 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
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
должен это сделать.
y = 0;
for(i = 15; i >= 0; i--) {
if((1 << i) & x) {
y |= 3;
}
y <<= 2;
}