7

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 :

9310 ( is divisible by 3)
010111012

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 ?

Community
  • 1
  • 1
Royi Namir
  • 144,742
  • 138
  • 468
  • 792
  • 1
    There is an explanation here: http://www.icodeguru.com/Embedded/Hacker's-Delight/065.htm – xanatos Aug 12 '15 at 06:55
  • 2
    Note that I consider it to be "high magic" :-) – xanatos Aug 12 '15 at 06:56
  • @xanatos I was hoping for less _formulas_ explanation :-). But I will read it thank you. – Royi Namir Aug 12 '15 at 06:58
  • May I ask what traits of the expression `((int) (i * 0x55555556L >> 30) & 3) == 0;` is better/bigger than the expression `i%3==0`? It does not seem to be faster on most architectures. But it is really unreadable. – wigy Aug 12 '15 at 06:59
  • @wigy Learning my friend. just learning with curiosity.Nothing more. – Royi Namir Aug 12 '15 at 07:00
  • Note that the formula you gave is different than the one suggested in the link: in the link they try to get the result of the division and from that the remainder... They shift by 32. Here you shift by 30 and analyze the result – xanatos Aug 12 '15 at 07:03
  • @xanatos I assume you're talking about the counting bits of even and odd places example — yes. At the end there should be another digest of the result. which is useless actually compared to the one single expression which checks mod3 or not. I just thought that they _might_ be related. – Royi Namir Aug 12 '15 at 07:05
  • Better explanation, with the example you used: http://www.hackersdelight.org/divcMore.pdf at page 19 "Remainder by Multiplication and Shifting Right"... they use `0x55555555` but the principle is the same (uint.MaxValue / 3 == 0x55555555.4) – xanatos Aug 12 '15 at 07:09

2 Answers2

4

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.

chiastic-security
  • 20,430
  • 4
  • 39
  • 67
  • I did understand the addition of `11` and if it was previously set , then the value is increased with 1 . but how's ` i * 0x55555556L >> 30` get's into this ? – Royi Namir Aug 12 '15 at 14:22
  • @njuffa Now I'm afraid that the answer doesn't answer the actual question `i * 0x55555556L >> 30`. Such details should have been mentioned. I asked explicitly how does `i * 0x55555556L >> 30` work. – Royi Namir Aug 12 '15 at 19:16
  • I did not mean to imply the answer is incorrect, and I have not reasoned through every detail of the code. I observe, however, that `i%3 = i - 3 * (i / 3)`. 2**32 * 1/3 = 0x55555555 (rounded down), 0x55555556 (rounded up), and if we perform the preceding computation in 32.32 fixed-point we would expect the remainder to be in the two topmost bits of the fraction stored in the lower 32 bits of the 32.32 bit result. This would explain the right shift by 30 to extract these bits. We don't need the integral portion of the fixed-point operands, so they can be omitted. – njuffa Aug 12 '15 at 19:54
  • Experimentally, the method based on integer multiplication works correctly only for i < 0x60000000. This makes sense as the accumulated rounding errors from representing 1/3 as 0x55555556 "overwhelm" the most significant fraction bits of the 32.32 fixed-point computation at that point. – njuffa Aug 12 '15 at 20:36
  • @njuffa can you please post this information as an answer ? – Royi Namir Aug 19 '15 at 06:31
  • I will consider it. I don't think I have sufficiently vetted what I outlined above to have it rise to the level of quality needed for an answer. The other reason I was uncomfortable posting an answer is that I am a C/C++ man, not a Java/C# guy. – njuffa Aug 19 '15 at 06:50
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 232*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.

njuffa
  • 23,970
  • 4
  • 78
  • 130