# Implementing x / 6 Using Only Bit Manipulations

** Published:**

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

## 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:

Thus we can calculate this(*Formula 2*)

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 \rfloor$. We can counter the error by this(*Formula 3*)

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

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);
}
```

## Leave a Comment