Check division by 3 with binary operations?

Question

I 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 ​​as well.

Obviously we can do:

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

But the interesting part was another calculation:

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

For simplicity:

0x55555556L = "1010101010101010101010101010110"

Nb

There is also another way to check:

You can determine if an integer is divisible by 3, counting 1 bit in the position of the odd bit, multiply this number by 2, add the number 1 bit in even bit positions, add them to the result and check, the result is divided by 3

For instance:

93 ₁₀ (divided by 3)
01011101 <sub> 2sub>

It has bit 2 in odd places and 4 bits in even places (place is zero based on base 2 )

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

At first I thought that these 2 methods are connected, but I did not find how to do this.

Question

how

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

- actually determines if i%3==0 ?

Answer 1

These two methods are not related to each other. The bitwise method is apparently associated with some methods of efficiently calculating modulo b-1 using the digital base b , known in decimal arithmetic as "expelling nines . "

The method based on multiplication is directly based on the definition of division when it is performed by multiplication by the inverse. Denoting / 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 part of the mathematical factor is converted directly to 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 that we only need to study fractional part of the private.

Instead of dividing by 3, we can multiply by 1/3. If we perform the calculation in 32.32 with a fixed point, 1/3 corresponds to 2 ³² * 1/3, which is a number between 0x55555555 and 0x55555556 . For reasons that will become obvious in the near future, we use revaluation here, that is, the result of rounding 0x555555556 .

When we multiply 0x55555556 by i , the most significant 32 bits of the full 64-bit product will contain the integral part of the quotient (int)(i * 1/3) = (int)(i / 3) . We are not interested in this integral part, so we do not calculate and store it. The lower 32 bits of the product are one of the fractions 0/3, 1/3, 2/3, however, they are calculated with a small error, since our value 0x555555556 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 look at the most significant bits of the three possible fraction values ​​in binary format, we find 0x5 = 0101 , 0xA = 1010 , 0x0 = 0000 . Thus, the two most significant bits of the fractional part of the factor exactly correspond to the desired modulo values. Since we are dealing with 32-bit operands, we can extract these two bits with a right shift of 30 bits, followed by a 0x3 mask to isolate the two bits. I think masking is necessary in Java, since 32-bit integers are always signed. For uint32_t operands in C / C ++, one shift is enough.

Now we see why the choice is 0x55555555 , since 1/3 view will not work. The fractional part of the factor would turn into 0xFFFFFFF* , and since 0xF = 1111 in binary terms, modular calculation will return an incorrect result of 3.

Note that as i increases, the accumulated error from the inaccurate 1/3 representation affects more and more bits of the fractional part. In fact, exhaustive testing shows that the method only works for i < 0x60000000 : beyond this limit, the error overflows the most significant bit bits that represent our result.

Answer 2

Whenever you add 3 to a number, you add binary 11 . Regardless of the original value of the number, this will maintain an invariant that is two times the number 1 bit in odd positions, plus the number 1 bit in even positions, will also be divided by 3.

You can see it that way. Let me invoke the value of the above expression c . You add 1 to the odd position and 1 to the even position. When you add 1 to an even position, either the bit you added 1 was set or not set. If it was canceled, you increase the value of c by 1 because you added the new 1 to the odd position. If it was set earlier, you will invert this bit, but add 1 to the even position (from transfer). This means that you first decrease c by 1, but now that you add 1 to an even position, you increase c by 2, so in general you increased c by 2.

Of course, this carry bit can also be added to the bit that is already set, in which case we need to check that this part is still increasing c by 2: you delete 1 in the even position (decrease c by 2), and then add a 1 to an odd position (increasing c by 1), which means that we actually reduced c by 1. This is the same as increasing c by 2, although if we work modulo 3.

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