CODEWITHSUNDEEP
algorithm
Ajay Pathak
Ajay Pathak

Reputation: 23

Perfect power of two between two numbers

How can I find perfect power of two between two numbers? Sample input: 0 and 10 Output: 2, 4, 8

Upvotes: 2

Views: 1680

Answers (6)

Jaye
Jaye

Reputation: 1

int first=0; //**first number which is a complete power of 2 in the range!**
 for(i=low;i<high;i++){
  if(2i==(i^(i-1)+1)){
   first=i;
   break;
  }
 }

while(first!=0){
 print first;
 first*=2;
 if(first>high){
  break;
}
}

Upvotes: 0

Voo
Voo

Reputation: 30216

Well the interesting part is "How do I get the greatest power of 2 that is less than or equal to my upper bound" and the same for the lowest power of 2 that is greater or equal to the lower bound.

And well, that's easily done without loops. For unsigned 32bit numbers:

floor(x):   ; floor power of 2
    x = x | (x >> 1)
    x = x | (x >> 2)
    x = x | (x >> 4)
    x = x | (x >> 8)
    x = x | (x >> 16)
    return x - (x >> 1)

ceil(x):   ; ceiling power of 2
    x = x - 1
    x = x | (x >> 1)
    x = x | (x >> 2)
    x = x | (x >> 4)
    x = x | (x >> 8)
    x = x | (x >> 16)
    return x + 1

You won't get around the loop for outputting the numbers though, but oh well.

Upvotes: 1

Rumple Stiltskin
Rumple Stiltskin

Reputation: 10405

Steps :

  1. Let's say n1 = start_of_range, n2 = end_of_range.
  2. Find out how many bits are needed to represent n1. Call it b.
  3. Now 2**b will be the next power of two after n1.
  4. It should be easy to calculate all the power of twos till n2 from this.

Sample python code :

#!/usr/bin/python
def get_bits(n):
    b = 0
    while n:
        n = n / 2
        b += 1
    return b

def get_power_of_two_in_range(n1, n2):
    b = get_bits(n1)
    x = 2**b
    res = []
    while x < n2:
        res.append(x)
        x = x * 2
    return res

def main():
    print get_power_of_two_in_range(0, 10)

if __name__ == '__main__':
    main()

Upvotes: 0

schnaader
schnaader

Reputation: 49719

You can use the binary representations of the numbers and output all the numbers between where only one bit is set:

0  = 00000000
10 = 00001010

=>

     00000001 (1)
     00000010 (2)
     00000100 (4)
     00001000 (8)

So your problem is reduced to finding the first power of two larger than the minimum and then shifting left while you're smaller than the maximum. Alternatively, unset all the set bits in the maximum value except the highest one and then shift right while you're larger than the minimum.

Upvotes: 1

Armen Tsirunyan
Armen Tsirunyan

Reputation: 133024

Find the highest bit set to 1 in first number, say it is at position x counting from lowest bit. Then find the highest bit set to 1 in the second number, say it is at position y. The numbers 2x+1, 2x+2..., 2y are the numbers you're looking for

Upvotes: 3

mbatchkarov
mbatchkarov

Reputation: 16049

How many times can you bit-shift before getting to 0?

Upvotes: 0

Related Questions