divide by 7 efficiently

[krypto_wizard]

How to divide a number by 7 efficiently without using - or / operator. We can use the bit operators. I was thinking about bit shift operator but I don't know the correct answer.

[lloyd mcclendon]

wait i forgot we can't use /

LOL

[Wybiral]

Well, bit shifts work great for fast power of two division/multiplication, such as...

x>>1  = x/2
x>>2  = x/4
x>>3  = x/8
x>>4  = x/16
x>>5  = x/32
x>>6  = x/64
x>>7  = x/128
x>>8  = x/256
x>>9  = x/512
x>>10 = x/1024

x<<1  = x*2
x<<2  = x*4
x<<3  = x*8
x<<4  = x*16
x<<5  = x*32
x<<6  = x*64
x<<7  = x*128
x<<8  = x*256
x<<9  = x*512
x<<10 = x*1024

But only power of two numbers, I don't know of any way that you can use them for non-power of twos (because of how they work).

0001 = 1
(0001 << 1) = 0010 = 2
(0010 << 1) = 0100 = 4
(0100 >> 2) = 0001 = 1

Bit shifts only work for integer numbers too.

[amo-ej1]

But you can use approximations that way.

1/7 = 0.142857

Now 1/8 + 1/64 = 0.140625
Or
1/8+1/64+1/512 = 0.142578

[krypto_wizard]

I think your solution is the closest I can get.

Thanks

[Klipt]

If you want to divide n by 7 you could do a binary search for the x that satisfies x*7 = n. Binary search requires being able to divide by 2, but that's easy with bitshifting (x/2 = x>>1)

[Lux Perpetua]

There are also recursive algorithms based on binary representation. For example, think of how you might get x/7 and x%7 if you had (x/2)/7 and (x/2)%7 from a recursive call. The way I'm thinking of traditionally requires some subtraction, but since your divisor is always 7, you can get around it.

It might help to think of it this way: (a/b)*b + (a%b) == a.

[Ragazzo]

Or to be simple, multiply by 0.142857

[lloyd mcclendon]

^ yeah but what's the point of that. at some point you used a / somewhere.

how about efficient division by N without using / or -

[Npl]

int32_t result = (int32_t)(((int64_t)x * 613566757U) >> 32)

This is (at least) exact for values smaller than 2^24. afterwards you can have a result thats 1 lower as the exact calculation (its still exact for most values).