CODEWITHSUNDEEP
binaryinteger-division
Snoop Catt
Snoop Catt

Reputation: 2329

How to divide an integer by 3 using binary operations

Similar question: How to know if a binary number divides by 3?

But how to actually divide a number by 3, efficiently, using only binary operations?

Upvotes: 0

Views: 373

Answers (1)

Snoop Catt
Snoop Catt

Reputation: 2329

The main idea is the following observation:

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

and to keep in mind that division by 4 is a simple binary operation (two bit shifts). Now, since we're dealing with integers, which may not be dividable by powers of 4, we have to make proper modifications. Let x_0 be an integer dividable by 3. We have:

x_0 = 4*q_0 + r_0

where q_0 = x_0 // 4 and r_0 = x_0 % 4, or in other words, q_0 = x_0 >> 2, r_0 = x_0 & 0b11.

For this q_0, we have

x_0 - 3*q_0 = q_0 + r_0

We add q_0 to an accumulating sum, and now we're left to divide x_1 := q_0 + r_0, which we know is dividable by 3, and is smaller (by roughly two bits) than x_0. Iterating this idea while x_k > 3, the induced sequence

q_0 + q_1 + ... + q_k

adds up to the desired result, x_0 / 3.

So as for operations, we had: bit-shifts, AND and addition. Additions are simply implemented with binary operations, using AND and XOR. Here is some code:

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 & 0b11
        sum = binary_sum(sum, q)
        x = binary_sum(q, r)

    return sum

Upvotes: 0

Related Questions