Is there a fast way do determine if an integer is a power of 2?

If possible one without jumps.

If possible one without jumps.

Not tested but here goes:

4 = 100

4 - 1 = 3 = 011

100

011

----

000 zero flag set!!!! 4 is a power of 2

15 = 1111

15 - 1 = 14 = 1110

1111

1110

-----

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

16 = 10000

16 - 1 = 15 = 01111

10000

01111

------

00000 zero flag set!!! 16 is a power of 2

:) Sorry If I made a mistake on this one.

```
```

.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

**AND**ing 4 and 3100

011

----

000 zero flag set!!!! 4 is a power of 2

**Example 2:**15 = 1111

15 - 1 = 14 = 1110

**AND**ing 15 and 141111

1110

-----

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

**Example 3:**16 = 10000

16 - 1 = 15 = 01111

**AND**ing 16 and 1510000

01111

------

00000 zero flag set!!! 16 is a power of 2

:) Sorry If I made a mistake on this one.

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

:)

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

:)

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

; 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

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

;)

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

;)

Couldn't you just write:

{clip}

I guess your confused with a multiple of two?

*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

Mine doesn't work? uhh I think it works perfectly.

Compile this proggy to test and try replacing the value with 5. This will popup yes (meaning 5 is a power of 2) :)

```
```

.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) :)

**stryker**, nice try. Try ZERO?

0 AND -1 = 0, ERROR!

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

;)

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

;)

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.

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]

```
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:

```
```

; 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

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

Regards,

hutch@movsd.com

Simple

Traditionally a non-zero value is TRUE, so you'd have to call this proc IsNotPowerOfTwo() for it to make sense. ;)

```
```

;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. ;)

If you just HAD to have it return a traditional bool:

Edit: Oops sorry. I see that somebody already posted a better version. Missed it first time around.

```
```

;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.

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.

- 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.

Stryker - Powers of two:

2^0 = 1

2^1 = 2

2^2 = 4

2^3 = 8

2^4 = 16

etc...

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

"2^3 = 8" ( Eight

"3^2 = 9" ( Nine is a power of three )

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 )

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. :)

I mistook it as power of x it should be root of x. :)