Is there a fast way do determine if an integer is a power of 2?
If possible one without jumps.
Posted on 2002-03-15 15:13:40 by dxantos
Not tested but here goes:


.data
nValue DD 16
.code
mov edx, nValue
mov eax, nValue
dec eax
and eax, edx
jnz @@NotPowerof2



Example 1:

4 = 100

4 - 1 = 3 = 011

ANDing 4 and 3

100
011
----
000 zero flag set!!!! 4 is a power of 2

Example 2:

15 = 1111

15 - 1 = 14 = 1110

ANDing 15 and 14

1111
1110
-----
1110 zero flag not set!!!! 15 isn't a power of 2

Example 3:

16 = 10000

16 - 1 = 15 = 01111

ANDing 16 and 15

10000
01111
------
00000 zero flag set!!! 16 is a power of 2


:) Sorry If I made a mistake on this one.
Posted on 2002-03-15 15:43:36 by stryker
I would test the bits 1 by 1,
If there are two bits set, its no power of 2.
If there is 1 bit set, its a power of 2.

2^0=1 this is also a power of 2

dont ask me how to do it in code

:)
Posted on 2002-03-15 15:52:58 by Jurgen
This isn't the best, but I just pulled it out of my hat...

; check if EAX is a power of 2
mov edx, eax
dec eax ; 2^x - 1
mov ecx, eax
not eax
shl eax,1
xor eax,ecx
xor eax, edx
; if EAX is -1, then power of two

inc eax
je PowerOfTwo
Posted on 2002-03-15 16:09:54 by bitRAKE
Couldn't you just write:

mov eax,value
test eax,1 ;is it a power of one ?
je ;yes, then jump to Power of one.
xxx ;no, it's a power of two
xxx


;)
Posted on 2002-03-15 16:37:03 by The SharK

Couldn't you just write:
{clip}
No, that only checks for odd/even, not a power of two.
I guess your confused with a multiple of two?
Posted on 2002-03-15 17:05:21 by bitRAKE
Originally posted by stryker

4 = 1000

am I missing something here 4 = 1000 ?
is the binary number of 4 = 0100
and the binary number of 3 = 0011
Posted on 2002-03-15 17:19:54 by The SharK
Mine doesn't work? uhh I think it works perfectly.



.586
.model flat, stdcall
OPTION SCOPED
OPTION CASEMAP:NONE

INCLUDE \masm32\include\kernel32.inc
INCLUDELIB \masm32\lib\kernel32.lib
INCLUDE \masm32\include\user32.inc
INCLUDELIB \masm32\lib\user32.lib

.DATA

notp2 DB "Not", 0
yesp2 DB "Yes", 0
value DD 6

.CODE

Start:

mov eax,value
test eax,1
je @PowerOfOne

;mov edx,value
;mov eax,value
;dec eax
;and eax, edx
;jnz @PowerOfOne

invoke MessageBox, 0, OFFSET yesp2, 0, 0
jmp @@Exit

@PowerOfOne:

invoke MessageBox, 0, OFFSET notp2, 0, 0

@@Exit:

invoke ExitProcess, 0

END Start


Compile this proggy to test and try replacing the value with 5. This will popup yes (meaning 5 is a power of 2) :)
Posted on 2002-03-15 17:23:48 by stryker
stryker, nice try. Try ZERO?

0 AND -1 = 0, ERROR!
Posted on 2002-03-15 17:30:32 by bitRAKE
Hello Stryker !

I didn't write anything about your code didn't work!

I only pointed out that:


am I missing something here 4 = 1000 ?
isn't the binary number of 4 = 0100
and the binary number of 3 = 0011


Regards,

The SharK

http://home19.inet.tele.dk/assembler

;)
Posted on 2002-03-15 17:32:32 by The SharK
Sorry!!! Opps, he he !!! that code above is not "reliable". Maybe it'll be better go with FPU instruction fsqrt and check if it's a whole number.
Posted on 2002-03-15 17:56:22 by stryker
This one will determine if a value is root of 2. Not the power of 2. :)




[size=9]
.586
.MODEL FLAT, STDCALL
OPTION SCOPED
OPTION CASEMAP:NONE

INCLUDE \masm32\include\kernel32.inc
INCLUDELIB \masm32\lib\kernel32.lib
INCLUDE \masm32\include\user32.inc
INCLUDELIB \masm32\lib\user32.lib

.DATA

notp2 DB "Not", 0
yesp2 DB "Yes", 0

value REAL8 16.0

.CODE

Start:

fld value
fsqrt
fstp value
fld value
frndint
fcomp value
fstsw ax
sahf
fstp value ;Rebalance FPU stack
jne @@NotPowerOf2

invoke MessageBox, 0, OFFSET yesp2, 0, 0
jmp @@Exit

@@NotPowerOf2:

invoke MessageBox, 0, OFFSET notp2, 0, 0

@@Exit:

invoke ExitProcess, 0

END Start
[/size]

Posted on 2002-03-15 18:39:05 by stryker
PowerOfTwo MACRO regmem:REQ

;; return EAX zero if regmem is a power of two
mov eax, regmem
sub eax, 1
sbb edx,edx
and eax, regmem
xor eax, edx
ENDM
stryker, thanks for the idea. :)
Mirno, haste makes waste... :tongue:
Posted on 2002-03-15 19:59:51 by bitRAKE


; Value to test in eax
; We will splatter ecx, so make sure nothing in there!

bsf ecx, eax
jnz NoBitsSet

btr eax, ecx
bsf ecx, eax

jnz PowerOfTwo


If you count zero as a power of 2, then you can get rid of the "jnz NoBitsSet"...

Beware, this code will be quite slow on anything less than a PPro/P2!

----- Edit -----
Alternative (non-destructive)


bsf ecx, eax
;jnz NoBitsSet ;Optional
bsr edx, eax
cmp edx, ecx
jne NonPowerOfTwo


As for BitRAKEs method, why not:


PowerOfTwo MACRO regmem:REQ
;; return EAX zero if regmem is a power of two
mov eax, regmem
; mov edx, regmem ;Not needed
dec eax
sbb edx,edx
and eax, regmem
xor eax, edx
ENDM


Or even:


mov edx, eax
dec eax
and eax, edx
; eax zero of powers of 2, non-zero for not


Mirno
Posted on 2002-03-15 20:02:41 by Mirno
Its easy enough to test if its NOT a power of two, SHL SHR by whatever amount you want and see if the value is the same after.

Regards,

hutch@movsd.com
Posted on 2002-03-15 20:32:10 by hutch--
Simple


;on exit if number is a power of two,
;eax = zero, otherwise eax = non zero
;
;
mov eax, number ;load number to test


bsf ecx, eax ;find position of 1st on bit
;if no bits present, eax = 0

shr eax, cl ;shift the bit down
;if eax = 0 this does nothing.

dec eax ;if there was only 1 bit, eax = 1
; so dec eax would be zero



Traditionally a non-zero value is TRUE, so you'd have to call this proc IsNotPowerOfTwo() for it to make sense. ;)
Posted on 2002-03-15 22:31:54 by iblis
If you just HAD to have it return a traditional bool:



;bool IsPwr2( unsigned int )
;
;In - dword to test
;out - type bool. 1 = is. 0 = is not.
;
IsPwr2 proc number:DWORD
mov eax, number
bsf ecx, eax
shr eax, cl
cmp eax, 1
je @F
xor eax, eax
@@: ret
IsPwr2 endp



Edit: Oops sorry. I see that somebody already posted a better version. Missed it first time around.
Posted on 2002-03-15 23:01:14 by iblis
hmm! I tested that algo but it returned something that it shouldn't.

- Number 0 it returned 0. 0 is a power of 2 ==> 0^2 = 0.
- Number 8 it returned 1. 8 is a power of 3 ==> 2^3 = 8.
- Number 9 it returned 0. 9 is a power of 2 ==> 3^2 = 9.

This is also where my first code fell(check the first reply). The numbers 0, 8 and 9 always screws up my first algo. The last stable solution I tested was the FPU code.
Posted on 2002-03-15 23:24:25 by stryker
Stryker - Powers of two:

2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
etc...



- Number 0 it returned 0. 0 is a power of 2 ==> 0^2 = 0

"0^2 = 0" ( Zero is a power of zero )

- Number 8 it returned 1. 8 is a power of 3 ==> 2^3 = 8

"2^3 = 8" ( Eight is a power of 2 )

- Number 9 it returned 0. 9 is a power of 2 ==> 3^2 = 9.

"3^2 = 9" ( Nine is a power of three )
Posted on 2002-03-15 23:31:39 by iblis
Oh sorry what was I thinking :) Geez!!! I need to clear my head :) Since I got caught with the functions i'm creating right now on determining n power. :)


I mistook it as power of x it should be root of x. :)
Posted on 2002-03-15 23:39:12 by stryker