Получите номер бит, который отличается от двух (двоичных) чисел

Question

У меня есть два числа (бинарные или нет, не играет никакой роли), которые отличаются только одним битом, например. (Псевдокод)

a = 11111111 
b = 11011111 

Я хочу простую функцию питона, которая возвращает битовую позицию, отличающуюся («5» в данном примере, если смотреть справа налево). Мое решение будет (питон)

math.log(abs(a-b))/math.log(2) 

, но мне интересно, если есть более элегантный способ сделать это (без использования поплавков и т.д.).

Благодаря Alex

Answer 1

Вы можете использовать бинарный эксклюзив:

a = 0b11111111 
b = 0b11011111 

diff = a^b # 0b100000 
diff.bit_length()-1 # 5 (the first position (backwards) which differs, 0 if a==b) 

Answer 2

без использования битовые операции, которые вы могли бы сделать что-то вроде этого:

In [1]: def difbit(a, b): 
    ...:  if a == b: return None 
    ...:  i = 0 
    ...:  while a%2 == b%2: 
    ...:   i += 1 
    ...:   a //= 2 
    ...:   b //= 2 
    ...:  return i 
    ...: 

In [2]: difbit(0b11111111, 0b11011111) 
Out[2]: 5 

Answer 3

, если я не хватает чего-то .. .

это должно работать:

>>> def find_bit(a,b): 
    a = a[::-1] 
    b = b[::-1] 
    for i in xrange(len(a)): 
     if a[i] != b[i]: 
      return i 
    return None 

>>> a = "11111111" 
>>> b = "11011111" 
>>> find_bit(a,b) 
5 

Возможно, это не так элегантно, но его легко понять, и он выполняет свою работу.

Answer 4

Использование (a^b).bit_length()-1 идеально подходит для чисел, которые имеют только один бит различия. EX:

a = 1000000 
b = 1000001 
(a^b).bit_length()-1 
Output: 0 

Но для чисел, которые имеют несколько разностных бит, он дает индекс левого большинства разностных бит. EX:

a = 111111111111111111111111111111 
b = 111111110111011111111111111111 
c = a^b # 1000100000000000000000 
c.bit_length()-1 
Output: 21 # Instead of 17. 21 is the left most difference bit 

Чтобы решить эту проблему, нам нужно изолировать правый бит, а затем получить его индекс. Таким образом, с помощью ((a^b) & (-(a^b))).bit_length()-1 лучше всего работает для всех входов:

c = (a^b) & (-(a^b)) # 100000000000000000 - Isolates the rightmost set bit 
c.bit_length()-1 
Output: 17 
(a^b) & (-(a^b))).bit_length()-1 
Output: 17 

Узнайте о выделении самый правый набор бит от here