CODEWITHSUNDEEP
cnumbers
Manish Kumar
Manish Kumar

Reputation: 1469

Division by 3 without division operator

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 ?

Upvotes: 1

Views: 352

Answers (1)

Potatoswatter
Potatoswatter

Reputation: 137770

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.)

Upvotes: 10

Related Questions