Divison by 7 using bitwise operators only.

[Aftabpasha]

Is it possible to find (integer) result of divison of a number by 7 by using Bitwise operators only? Please give a method to do so. Thank you.

[arnaudk]

Have a look at "Egyptian division".

[JosAH]

Have a look at "Egyptian division".

Cute; you can even avoid the multiplication by seven by shifting like this:

int times_seven(int x) { return (x<<3)-x; }
 

We still do need addition (and subtraction) though ...

kind regards,

Jos

[Banfa]

I rather like the method dividing by shift and subtraction

Assuming you are dividing N by 7 then

1. Divisor D = 7
2. Shift D left until the D > N.
3. Shift D right 1 place
4. IF D >= N { Record a 1, subtract D from N } ELSE { Record a 0 }
5. IF D != 7 { GOTO 3 }
6. END You record sequence 1s and 0s is the result MSB first and N now contains the remainder

Example

What is 183 / 7?
 
In binary
10110111 / 111
 
1. D = 111
2. Shift divisor D until D > N (10110111): D = 11100000
3. Shift D right 1 place: 1110000
4. D >= N: Record 1, N -= D: N = 10110111 - 1110000 = 1000111
5. D != 111: GOTO 3
3. Shift D right 1 place: 111000
4. D >= N: Record 1, N -= D: N = 1000111 - 111000 = 1111
5. D != 111: GOTO 3
3. Shift D right 1 place: 11100
4. D < N: Record 0
5. D != 111: GOTO 3
3. Shift D right 1 place: 1110
4. D >= N: Record 1, N -= D: N = 1111 - 1110 = 1
5. D != 111: GOTO 3
3. Shift D right 1 place: 111
4. D < N: Record 0
5. D == 111
6. Result 11010 N = the remainder = 1
 
11010 = 26 so
 
183 / 7 = 26 r 1
 

I'm not sure if this is the method already suggested only in different terms or if this method is particularly efficient.

[r035198x]

... by using Bitwise operators only? .....

That may well mean comparison, - and + are not allowed.

[Banfa]

That may well mean comparison, - and + are not allowed.

How about if you can implement addition through bitwise operators for instance

Adding A plus B

Calculate A' = A xor B
Calculate B' = A and B

If B' == 0 result = A'

else A = A', B = B' << 1 and iterate

Subtraction can be by by adding of a negative value, that is negate the value to subtract (by inverting all bits and adding 1) and then add it to the other value.


It can all be done, basically it is a computer, it holds data as bits so ultimately everything by definition is a bitwise operation :D

[JosAH]

I'm not sure if this is the method already suggested only in different terms or if this method is particularly efficient.

It's the Egyptian division method; those faraos were clever dickies in their time ;-)

kind regards,

Jos

[Pragma]

What do these links have to do with this particular thread?

kind regards,

Jos (moderator)

ps. I'll remove your (and my) reply if my reply isn't answered in a reasonable time span.

This is most definitely spam. I used to moderate the board of a student .org back in college and we would get those sometimes. They post those links so that when the Google bot crawls the forum it increases their page rank.

[JosAH]

This is most definitely spam. I used to moderate the board of a student .org back in college and we would get those sometimes. They post those links so that when the Google bot crawls the forum it increases their page rank.

Hi, I removed the message and my reply this morning; it is spam alright.

kind regards,

Jos