Как разделить целое число на 3 с помощью бинарных операций - PullRequest
Новая
       69

Как разделить целое число на 3 с помощью бинарных операций

0 голосов
/ 05 августа 2020

Аналогичный вопрос: Как узнать, делится ли двоичное число на 3?

Но как на самом деле эффективно разделить число на 3, используя только двоичные операции?

1 Ответ

0 голосов
/ 05 августа 2020

Основная идея заключается в следующем наблюдении: 

1/3 = 1/4 + 1/16 + 1/64 + ...

и мы помним, что деление на 4 является простой бинарной операцией (сдвиг на два бита). Теперь, поскольку мы имеем дело с целыми числами, которые могут не делиться на степень 4, мы должны внести соответствующие изменения. Пусть x_0 будет целым числом, делимым на 3. У нас есть: 

x_0 = 4*q_0 + r_0

, где q_0 = x_0 // 4 и r_0 = x_0% 4, или, другими словами, 

q_0 = x_0 >> 2, r_0 = x_0 & 3

Для это q_0, у нас есть 

x_0 - 3*q_0 = q_0 + r_0

Мы добавляем q_0 к сумме накопления, и теперь нам осталось разделить x_1: = q_0 + r_0, которое, как мы знаем, делится на 3 и меньше (на примерно два бита), чем x_0. Повторяя эту идею, пока x_k> 3, индуцированная последовательность 

q_0 + q_1 + ... + q_k

добавляет к желаемому результату x_0 / 3.

Итак, что касается операций, у нас были: битовые сдвиги, И и дополнение. Дополнения просто реализуются с помощью бинарных операций с использованием AND и XOR. Вот какой-то код: 

def binary_sum(a, b):
    
    while True:
        
        add = a ^ b         # '^' is XOR
        carry = a & b
        if carry == 0:
            break
        else:
            a = add
            b = carry << 1
    
    return add
        


def bin_division_by_3(x):
     
    sum = 1

    while x > 3:
        q, r = x >> 2, x & 3
        sum = binary_sum(sum, q)
        x = binary_sum(q, r)

    return sum
...