binary divide by 3

All arithmetic processes are built on those operations. However you may be thinking of an adaptation of double dabble. See dubldabl.txt at:

You can divide by multiplying by the reciprocal. 1/3 = .01010101...(binary). This can done with shifts and adds. This illustration assumes that x is an unsigned integer variable:

x += x >> 2; /* x * 1.01 */ x += x >> 4; /* x * 1.010101 */ x += x >> 8; /* x * 1.01010101010101 */ etc., to get as many bits as needed for input range x >>= 2; /* x * .0101010101010101 */

As a practical issue, you may want to round up to avoid the losses from truncation when bits are shifted off to the left:

x += (x+2) >> 2; x += (x+8) >> 4; x += (x+128) >> 8;

If you have an 8-bit value, only the first two terms are needed,

Notice that the way this is written, you can get an overflow if x*4/3 exceeds the capacity of the working variable.

Thad

Nice. This is a keeper.

performing

Alternatively:

n=2

Other cool n's would be n=4,8,16,32,... (1/5,1/9,1/17,1/33,...)

So in C:

#include

unsigned divideBy3(unsigned n) { unsigned ix = 1; unsigned nx = 0; unsigned temp; while (temp = n >> ix) { if (ix&1) nx += temp; else nx -= temp; ++ ix; } return nx; }

unsigned diffs[21] = {0};

int main() { unsigned ix = 0xFFFFFFF; int diff = -9; unsigned* pdiffs = diffs +10; while (ix) { int diffx = divideBy3(ix) - ix/3; if (diffx > -9 && diffx < 10) pdiffs[diffx] ++; -- ix; } while (diff < 10) { printf("%d - %u\n", diff, pdiffs[diff]); ++ diff; } return ix; }

There can be a difference of -4 to 5 due to truncation of bits when shifting.

Output: (Distribution of differerences)

-9 - 0

-8 - 0

-7 - 0

-6 - 0

-5 - 0

-4 - 407

-3 - 122031

-2 - 4668885

-1 - 41504190