What is a bit-shifting standard C function for calculating $f(x) = \frac{(2^{16}- 1)}{(2^{32} - 1)}\cdot x$

Question

I need to take 32-bit unsigned integers and scale them to 16-bit unsigned integers "evenly" so that $0 \mapsto 0$ and 0xFFFFFFFF $\mapsto$ 0xFFFF. I also want to do this without using a 64-bit unsigned integer built-in type.

To give you an idea, going in the opposite direction, the formula for 16-bit to 32-bit scaling is:

U16 y = 0x3290;   // example input
U32 x = ((U32)y << 16) + y;      // formula implementation

To arrive at the formula in the title, I simply took two points on the line that is the graph of $f$, and calculated the slope and y-intercept, like in Alg 1.

Those are the rules. Good luck!

Answer 1

Note that $$\frac{2^{16}-1}{2^{32}-1}=\frac{1}{2^{16}+1}=2^{-16}\frac{1}{1+2^{-16}}=2^{-16}(1-2^{-16}+2^{-32}-\ldots).$$ So rounding to the nearest integer the following is maybe what you intend:

$$x\mapsto(x - (x \gg 16) + \textrm{0x8000u}) \gg 16$$

That said, you're probably better off with the answer in the first comment: simply shift right. To see why, consider a related problem of mapping the real interval $[0,1)$ to integers in the range $[0,255]$. (For example to convert to eight bits per pixel images.) The best way is not $$x \mapsto \lfloor 255.0\, x + 0.5\rfloor$$ but simply $$x\mapsto \lfloor 256.0\, x\rfloor.$$ The first method assigns half as much to the bins $0$ and $255$ as to the others. The second method equally fills all bins.

Answer 2

Intuitively it seems like each 2-bits in the U32 correspond to each 1-bit in the U32 in the natural order. Take the first two values: 00, 01 to be 0, and the second two 10, 11 to be 1. So $\{00, 01, 10, 11\} \to \{0, 1\}$ with division by 2 and flooring.

There is no formula!!!!!!!!! ahhhhh

Resorting to dividing by $(2^{16} + 1)$ with U32 arithmetic division.

I've tried another approach too and that didn't help either. There might be something about dividing by $2^{16}$ first and deducing that it equals division by $2^{16} + 1$ on certain inputs that are within the range of a U32. Still accepting answers if you find a method.

Answer 3

You're probably better off asking this on a programming forum.

That said, simply doing division is probably your best bet: not only does it make it obvious what you are doing, but the compiler is likely to automatically convert it to bit shifts for you anyways. And even if it doesn't, there's a good chance that it doesn't even matter whether or not you are doing this calculation efficiently!

Note, incidentally, that you haven't specified how you want to do the rounding....

---

Anyways, the standard algorithm for converting division by arbitrary divisors into division by powers of $2$ (along with some multiplies and adds/subtracts) is called "Barrett reduction".