Implementing x / 6 Using Only Bit Manipulations

This is an interesting question from one of the lab assignments in Introduction to Computer Systems, fall 2018 at Peking University.

Problem Description

Given a 32-bit integer (x)(in two's complement), implement a C function that returns (frac{x}{6}) using ONLY bit manipulations(operators like ~ ! | ^ & << >> +). Your function should behave exactly as the C expression x/6.

Hint: You can use the following formula(Formula 1)

[2 = frac{2+1}{2} imes frac{2^2+1}{2^2} imes frac{2^4+1}{2^4} imesfrac{2^8+1}{2^8}... ]

Inspiration

Since division is very slow using hardware, compilers often use optimizations to speed up division. For example, gcc will replace x/6 with x*171/1024 when x is relatively small, and implement x*171/1024 with shift left and shift right instructions. However, our function must cover all 32-bit two's complement integers, which means some other techniques are needed to make such replacement possible.

Resolution

We can change Formula 1 into the following form:

[frac{1}{6} = frac{1}{8} imes frac{2^2+1}{2^2} imes frac{2^4+1}{2^4} imesfrac{2^8+1}{2^8}... ]

Thus we can calculate this(Formula 2)

[p = frac{x}{8} imes frac{2^2+1}{2^2} imes frac{2^4+1}{2^4} imesfrac{2^8+1}{2^8} imes frac{2^{16}+1}{2^{16}} ]

Which can be implmented using a combination of shift-right and add operations(note that you must program carefully to avoid overflows). However, errors occur since expressions like x>>y return (lfloor x/2^y floor). We can counter the error by this(Formula 3)

[frac{x}{6} = p + frac{x}{6} - p = p + frac{1}{6}(x-6p) ]

Since errors introduced by shift-rights will only cause (p) to be smaller than (frac{x}{6}), we can deduce that (x-6p > 0). You can then approximate an upper bound of (x-6p), which depends on your implementation of Formula 2.

Suppose that (x-6p < M)(where M is small), then we can approximate (frac{1}{6}) in Formula 3 using some (X approx frac{1}{6}) while keeping the equation true

[lfloor frac{1}{6} (x-6p) floor = lfloor X cdot (x-6p) floor ]

Choose a proper (X = a/2^b), and we are done!

/*
 * divSix - calculate x / 6 without using /
 *   Example: divSix(6) = 1,
 *            divSix(2147483647) = 357913941,
 *   Legal ops: ~ ! | ^ & << >> +
 *   Max ops: 40
 *   Rating: 4
 */
int divSix(int x) {
	int p;
	int q,y,t;
	x=x+(x>>31&5);
	p=x>>3;
	p=p+(p>>2);
	p=p+(p>>4);
	p=p+(p>>8);
	p=p+(p>>16);
	q=~p+1;
	t=x+(q<<1)+(q<<2);
	t=t+(t<<1)+(t<<3);
	return p+(t>>6);
}