Check division by 3 with binary operations?

Question

I've read this interesting answer about "Checking if a number is divisible by 3"

Although the answer is in Java , it seems to work with other languages also.

Obviously we can do :

boolean canBeDevidedBy3 = (i % 3) == 0;

But the interesting part was this other calculation :

boolean canBeDevidedBy3 = ((int) (i * 0x55555556L >> 30) & 3) == 0;

For simplicity :

0x55555556L = "1010101010101010101010101010110"

Nb

There's also another method to check it :

One can determine if an integer is divisible by 3 by counting the 1 bits at odd bit positions, multiply this number by 2, add the number of 1-bits at even bit positions add them to the result and check if the result is divisible by 3

For example :

93₁₀ ( is divisible by 3)
01011101₂

It has 2 bits in the odd places and 4 bits at the even places ( place is the zero based of the base 2 digit location)

So 2*1 + 4 = 6 which is divisible by 3.

At first I thought those 2 methods are related but I didn't find how.

Question

How does

  boolean canBeDevidedBy3 = ((int) (i * 0x55555556L >> 30) & 3) == 0;

— actually determines if i%3==0 ?

Answer 1

Whenever you add 3 to a number, what you do is to add binary 11. Whatever the original value of the number, this will maintain the invariant that twice the number of 1 bits at odd positions, plus the number of 1 bits at even positions, will also be divisible by 3.

You can see that in this way. Let's call the value of the above expression c. You're adding 1 to an odd position, and 1 to an even position. When you add 1 to an even position, either the bit you've added 1 to was set or unset. If it was unset, you'll increase the value of c by 1, because you've added a new 1 in an odd position. If it was previously set, you'll flip that bit, but add a 1 in an even position (from the carry). This means that you initially decrease c by 1, but now when you add the 1 in the even position, you increase c by 2, so overall you've increased c by 2.

Of course, this carry bit might also get added to a bit that's already set, in which case we need to check that this part still increases c by 2: you'll remove a 1 in an even position (decreasing c by 2), and then add a 1 in an odd position (increasing c by 1), meaning that we've in fact decreased c by 1. That is the same as increasing c by 2, though, if we're working modulo 3.

A more formal version of this would be structured as a proof by induction.

Answer 2

The two methods do not appear to be related. The bit-wise method seems to be related to certain methods for the efficient computation of modulo b-1 when using digit base b, known in decimal arithmetic as "casting out nines".

The multiplication-based method is directly based on the definition of division when accomplished by multiplication with the reciprocal. Letting / denote mathematical division, we have

int_quot = (int)(i / 3)
frac_quot = i / 3 - int_quot = i / 3 - (int)(i / 3)
i % 3 = 3 * frac_quot = 3 * (i / 3 - (int)(i / 3))

The fractional portion of the mathematical quotient translates directly into the remainder of integer division: If the fraction is 0, the remainder is 0, if the fraction is 1/3 the remainder is 1, if the fraction is 2/3 the remainder is 2. This means we only need to examine the fractional portion of the quotient.

Instead of dividing by 3, we can multiply by 1/3. If we perform the computation in a 32.32 fixed-point format, 1/3 corresponds to 2³²*1/3 which is a number between 0x55555555 and 0x55555556. For reasons that will become apparent shortly, we use the overestimation here, that is the rounded-up result 0x555555556.

When we multiply 0x55555556 by i, the most significant 32 bits of the full 64-bit product will contain the integral portion of the quotient (int)(i * 1/3) = (int)(i / 3). We are not interested in this integral portion, so we neither compute nor store it. The lower 32-bits of the product is one of the fractions 0/3, 1/3, 2/3 however computed with a slight error since our value of 0x555555556 is slightly larger than 1/3:

i = 1:  i * 0.55555556 = 0.555555556
i = 2:  i * 0.55555556 = 0.AAAAAAAAC
i = 3:  i * 0.55555556 = 1.000000002
i = 4:  i * 0.55555556 = 1.555555558
i = 5:  i * 0.55555556 = 1.AAAAAAAAE

If we examine the most significant bits of the three possible fraction values in binary, we find that 0x5 = 0101, 0xA = 1010, 0x0 = 0000. So the two most significant bits of the fractional portion of the quotient correspond exactly to the desired modulo values. Since we are dealing with 32-bit operands, we can extract these two bits with a right shift by 30 bits followed by a mask of 0x3 to isolate two bits. I think the masking is needed in Java as 32-bit integers are always signed. For uint32_t operands in C/C++ the shift alone would suffice.

We now see why choosing 0x55555555 as representation of 1/3 wouldn't work. The fractional portion of the quotient would turn into 0xFFFFFFF*, and since 0xF = 1111 in binary, the modulo computation would deliver an incorrect result of 3.

Note that as i increases in magnitude, the accumulated error from the imprecise representation of 1/3 affects more and more bits of the fractional portion. In fact, exhaustive testing shows that the method only works for i < 0x60000000: beyond that limit the error overwhelms the most significant fraction bits which represent our result.