1

I was given this question in an interview to describe the output in comments.

unsigned int d2(unsigned int a)
{
__int64 q = (__int64)a * 0x0AAAAAAAB;  // (2^33+1) / 3
return (unsigned int)(q >> 33);
}

I have checked other questions in Stackoverflow related to division by 3 but none seems so fast and small. Can anybody help me in explaining how the function is giving the output written in comments ?

Manish Kumar
  • 1,419
  • 3
  • 17
  • 36
  • Must have something to do with overflow. – Fiddling Bits Dec 08 '13 at 06:43
  • 1
    It is the binary equivalent of taking a number, multiplying it by 100000/3 which is about 33333, and then dividing by 100000, leaving it approximately equal to the original number divided by 3. – Max Dec 08 '13 at 06:45
  • 2
    Odd question for an interview :) – Cory Nelson Dec 08 '13 at 06:47
  • Eg: 66 * 33334 = 2200044, then shift the decimal point over, = 22.00044. Or, 22. We use 33334 so the number rounds up, otherwise you'd get 21.998... which truncates to 21. – Max Dec 08 '13 at 06:48
  • @CoryNelson: not really. It's not, as the OP believes, a C thing though: it's a very common compiler optimisation. Perhaps the interview was for a Reverse Engineering job. – Jongware Dec 08 '13 at 15:29
  • [Divide a number by 3 without using *, /, +, -, % operators](http://stackoverflow.com/q/11694546/995714) – phuclv Oct 27 '16 at 06:03

1 Answers1

10

The function divides a 32-bit unsigned number by 3.

If you multiply by 2^33 and then divide by 2^33 (by right shifting), then you get the original number. But if you multiply by (2^33)/3 and then divide by 2^33, you effectively divide by three.

The last digit is B instead of A to cause the result to be rounded up.

There is no need to actually write this in your code because the compiler will usually do this for you. Try it and see. (Furthermore, for a signed input, the compiler can safely generate a signed right shift, but the C language does not define such an operation.)

Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
  • q >> 33 is divided by 2^33, but how 0x0AAAAAAAB is 2^33/3 ?? – Manish Kumar Dec 08 '13 at 13:00
  • @Learner That's what it is… it's just a number. It's rounded up from the exact fraction. – Potatoswatter Dec 08 '13 at 13:07
  • There must be a way the number has come up. Could you please elaborate ? – Manish Kumar Dec 08 '13 at 13:19
  • @Learner Yes, by dividing 2^33 by 3 and rounding up. There's not more to it than that. One-third happens to be a repeating fraction, 0.AAAAA… in hexadecimal, just as it is 0.33333… in decimal, because neither 16^n nor 10^n is divisible by 3 for any n. – Potatoswatter Dec 08 '13 at 13:25
  • 1
    @Potatoswater: Thanks for explanations. I got one another way to derive this. I am thinking like this: if I multiply 0x55555555 with 3 it gives -1. and the 2's complement of 0x55555555 is 0xAAAAAAAB. And 0xAAAAAAAB is approx ~ 2^33/3. – Manish Kumar Dec 08 '13 at 13:33