Page 1 of 1
reverse binary number
Posted: Sat Jul 26, 2008 6:22 am
by etlam
hello,
I have a number and I need to have the binary digits reversed.
So if I have: 0...0101110 I want to have 0...0011101 (but if I have 011101000..., than this is also fine, since than I just divide. )
Is there a simpler way of computing the second number from the first one than doing this bit per bit?
Thanks in advance,
etlam
EDIT: I just noticed that I posted tis in the false forum, if a moderator could put it to Genaral Programming? thanks.
Sorry for my bad english
Re: reverse binary number
Posted: Sat Jul 26, 2008 6:43 am
by suthers
Download/Open the lintel manuals and have a look at the RCL/RCR/ROL/ROR-—Rotate part...
Jules
Re: reverse binary number
Posted: Sat Jul 26, 2008 9:29 am
by etlam
Thanks, but how does rotating help reversing the number?
I'm sorry if I have overseen something, but I don't see how to reverse the binary representation of a number with rotating.
Thanks in advance,
etlam
Re: reverse binary number
Posted: Sat Jul 26, 2008 9:50 am
by suthers
Sorry My fault, I didn't understand your post properly...
Jules
Re: reverse binary number
Posted: Sat Jul 26, 2008 11:06 am
by jnc100
Besides the obvious (portable) way of masking out each bit etc in a long loop in C, with x86 you can do:
(Intel Syntax, untested, cdecl)
Code: Select all
; unsigned long int reverse_bin(unsigned long src, unsigned long bitlength);
reverse_bin:
push ebp
mov ebp, esp
mov edx, [ebp + 8]
mov ecx, [ebp + 12]
xor eax, eax
.do_shift:rcl edx
rcr eax
loop .do_shift
pop ebp
ret
Regards,
John.
Re: reverse binary number
Posted: Sat Jul 26, 2008 11:28 am
by suthers
That's the sort of thing I was talking about, but it isn't computing, it's the same thing, except it will be faster than C because it uses optimized x86 instructions...
Jules
Re: reverse binary number
Posted: Sat Jul 26, 2008 12:10 pm
by stephenj
There are six methods describing how to reverse bits using
Bit Twiddling Hacks.
Re: reverse binary number
Posted: Sat Jul 26, 2008 12:21 pm
by suthers
OMG in three OPS....
How the hell does that work?
Jules
edit: sorry there's an explanation underneath, but I wouldn't have thought of that in 100 years
Re: reverse binary number
Posted: Sat Jul 26, 2008 12:42 pm
by bewing
@stephenj -- that's a hell of a nice link.
I just do it with a per-byte table lookup. If you do it more than once (so the table ends up in the cache) it's really fast.
Re: reverse binary number
Posted: Sat Jul 26, 2008 12:55 pm
by suthers
Found another way, but it's prone to accuracy due to rounding:
I haven't tested it completely, but I have a felling it could have rounding errors....
Jules
edit: This is for a byte obviously, to adapt it, all you have to do is change 255 to (2 ^ size_of_var) - 1... (I don't know why I'm saying this on forum...)
Re: reverse binary number
Posted: Sat Jul 26, 2008 1:02 pm
by suthers
Nope wrong again, works only for the one example I tried (F0)...
Jules
Re: reverse binary number
Posted: Sat Jul 26, 2008 1:55 pm
by codemastersnake
one slower and easy method would be:
# save binary in an array and reverse the string, then convert it back to binary.
Other would be:
# saving binary digit as a number like of integer datatype,
# then keep on dividing the number by then and get the remainfder until the number becomes zero (as we do in palindrome checking)
# save the remainder in another variable
# you have reversed binary digit!
Re: reverse binary number
Posted: Sun Jul 27, 2008 1:25 am
by etlam
Thank you all for the answers. They helped me a lot.
etlam
Re: reverse binary number
Posted: Sun Jul 27, 2008 12:02 pm
by chezzestix
This is more of a question than a suggestion:
Couldnt you just use XOR? Just XOR the number against the lagest possible number in the bit size.
11111111 - 255
XOR
00110001
Yeilds
11001110
So the code would look like
XOR al,255
or
XOR ax,65535
etc...
Im sure someone must have thought of this before me but why isnt it used? We use its brother AND to mask so why not apply it here?
[Edit]
*facepalm*
Re: reverse binary number
Posted: Sun Jul 27, 2008 12:05 pm
by suthers
chezzestix wrote:This is more of a question than a suggestion:
Couldnt you just use XOR? Just XOR the number against the lagest possible number in the bit size.
11111111 - 255
XOR
00110001
Yeilds
11001110
So the code would look like
XOR al,255
or
XOR ax,65535
etc...
Im sure someone must have thought of this before me but why isnt it used? We use its brother AND to mask so why not apply it here?
chezzestix, that's not what he wants to do, he want's to make the first bit the last bit, the last the first, the second the before last, etc...
not invert....
Jules