I'm trying to write a function that will take a two's compliment 32 bit int and return 1 if it is a power of 2 and 0 if it is not, does anyone have any help they could give me on this
Posted on 2002-10-16 21:55:38 by samps005
I guess just testing the coresponding bits will do... at least for positive numbers

What i mean is if the binary representation of the number has a single 1 bit on any position then it is a pure power of 2.
Posted on 2002-10-16 22:13:31 by BogdanOntanu
This was asked here before, but I couldn't find it.
Answer is:

mov ecx, eax
dec eax

and eax, ecx
;EAX = zero only if a single bit is set, or EAX = 0 on input EAX
;i.e. Must be a power of two.

Has been fixed - memory was a little rusty. :tongue:
Posted on 2002-10-16 22:44:37 by bitRAKE
Posted on 2002-10-17 01:24:09 by iblis
If I wanted to adjust this so it would test for powers of 4 would I just subtract 3 instead of 1. since 1 is 0001 and 3 is 0011?
Posted on 2002-10-17 06:44:31 by samps005
In a word: No.
x    x-3  x&(x-3)

0000 1101 0000
0001 1110 0000
0010 1111 0010
0011 0000 0000
0100 0001 0000
0101 0010 0000
0110 0011 0010
0111 0100 0100
1000 0101 0000
1001 0110 0000
1010 0111 0010
1011 1000 1000
1100 1001 1000




mov ecx, eax
dec ecx
test eax, ecx
jnz not_power_of_four
test eax, 055555555h
jz not_power_of_four


Of course you wouldn't mind telling us why you need to figure out this problem?
There are of course many reasons why you'd want such code, but the fact that this is coupled with such a fundamental mis-comprehension of binary arithmatic suggests to me that maybe we're doing someones homework... Especially as this is the only post to the board...

If it is homework, I hope you'll give credit to the appropriate members of the board when you hand it in.

Mirno
Posted on 2002-10-17 07:27:58 by Mirno
hey man you don't need to make fun of my lack of comprehension. I'm trying to learn how to program in assembly, and this was one of the practice problems I was having trouble understanding. If this board is for experts only then I'll not post here anymore
Posted on 2002-10-17 12:26:19 by samps005
samps005...to get only numbers that are a power of four:

They would be 4,16,64,256 for a byte

push em on the stack then pop them one at a time to compare with your byte

or you could multiply a value 4 in a register by 4 ...three times to compare to your byte

Since your using 32 bit integer just multiply a few more times.

Sounds like your sorting numbers.
Posted on 2002-10-17 13:01:27 by IwasTitan
This board isn't only for "experts", there are lots of guys new to assembly here (or were when they joined at least), but this board is not here to do your homework for you.

The fact that you don't seem comfortable with binary arithmetic made me suspect that you are solving this problem for some class, and I for one do not like the idea of getting someone else marks they don't deserve.

If you aren't doing this for some school problem, then I'm sorry, but it certainly looked like one after your misunderstanding of the logic involved. Also I would suggest that you try to go through the more fundamental aspects of logic, and binary arithmetic, they form the backbone of many seemingly complex algorithms. Of course this is the point, they seem complex until you learn the tricks of the trade, and the trade we are involved in here is the manipulation of binary data.
Other than that, there are an excelent set of tutorials that will teach you how to program in assembly (by Iczelion) included with masm32. They try to teach how to program in assembly, within the framework of the Windows 32 bit environment. They also do not try to weigh you down with optimisations early on in your assembly programming life. It is often said that early optimisation is the root of all evil, this is especially true when trying to learn the language you are attempting to optimise in.

Mirno
Posted on 2002-10-17 13:53:44 by Mirno
it's not for a class, I'm just trying to learn assembly on my own. Yeah I guess you right I don't really understand binary arithmetic that well.

anyway here is what I came up with this is in psuedo code, or c basically.

for power of 2 or not
!(((x + (~0x00)) & x) | (!x))
this returns 1 if power of 2 and 0 else. (i think)


for power of 4 or not
(!((x + (~0x00)) & x) & (!(x & 0xAAAAAAAA)))
this returns 1 if a power of 4 and 0 else (i think)

This seems to be working, does anyone see any more errors in my logic.
Posted on 2002-10-17 14:04:19 by samps005
you should listen to bitRAKE's post.. but if it's C that you want, do something on these lines:



/* Is an integer number a power of 2? */
#define ISPOW2(x) (x && (x & !(x-1)))
Posted on 2002-10-17 15:33:13 by Maverick
Maverick



/* Is an integer number a power of 2? */
#define ISPOW2(x) (x && (x & !(x-1)))


this doesn't seem to work for x = 2

my way might not look that pretty, but I'm run a large number of test cases and it seems to work.

it is basically what was posted in assembly earlier
Posted on 2002-10-17 16:02:32 by samps005
I don't know if it runs, the snippet is not mine.
Why not use bitRAKE's code? ;)
Posted on 2002-10-18 03:13:59 by Maverick
Maverick's macro should be:
#define ISPOW2(x) (x && !(x & (x-1)))


He'd put the ! too early :)

Mirno
Posted on 2002-10-18 05:20:05 by Mirno
This should work:



cmp eax, 0
jle not_p2
lea edx, [eax-1]
and eax, edx
jnz not_p2
inc eax
ret

not_p2:
xor eax, eax
ret


Number to test in EAX and result in EAX (1 if power of 2, 0 otherwise)
Posted on 2002-10-18 08:22:03 by gliptic