0

I have 2 similar pieces of code which take a number and return the next power of 2 They return the same result up until 1e9, any larger and the second function returns an incorrect answer, why is that?

unsigned long long nextPowerOf2(unsigned long long n) 
{ 
    unsigned long long p = 1; 
    if (n && !(n & (n - 1))) 
        return n; 
  
    while (p < n)  
        p <<= 1; 
      
    return p; 
}
unsigned long long nextPowerOf(unsigned long long n)  //returns incorrect answer if n>1e9
{  
    unsigned long long count = 0;  
      
    if (n && !(n & (n - 1)))  
        return n;  
      
    while( n != 0)  
    {  
        n >>= 1;  
        count += 1;  
    }  
    cout << "weird?: " << count << endl;
    return (1 << count);  
}
YosefAhab
  • 64
  • 10
  • 3
    `return (1 << count);` what happens if count is equal to or bigger than the bit size of int? Did you mean `return 1ULL << count;`? – Eljay Mar 27 '21 at 16:34
  • That did it, i didnt think it would matter since the function returns ull anyway and its not stored in a variable. so why is that? – YosefAhab Mar 27 '21 at 16:48
  • 1
    Especially when dealing with bitwise operations, it may be useful to express numbers in hexadecimal or binary instead of decimal. That tends to make it more obvious when you cross a "magic boundary" such as 2^32 (or 2^31 for signed values). – JaMiT Mar 27 '21 at 16:56
  • 1
    Does this answer your question? [Why does long long n = 2000\*2000\*2000\*2000; overflow?](https://stackoverflow.com/questions/66354756/why-does-long-long-n-2000200020002000-overflow) – JaMiT Mar 27 '21 at 17:01
  • 1
    @Yosefahab try `1ULL << count` instead. If you used clang (visual studio, etc) it would warn you that you're doing implicit casts. – Soleil Mar 27 '21 at 17:05
  • It seems like @JaMiT said 'magic boundary' that was crossed, i know anything bigger than 1e9 would overflow an integer thats why i specified my types as unsigned long long. Apparently you need to cast the return value to ULL explicitly even without a variable, i'm guessing thats compiler behaviour ? – YosefAhab Mar 27 '21 at 17:06
  • The `1 << count` results in an `int`. The evaluation of that expression is irrelevant that the return will be an `unsigned long long`. – Eljay Mar 27 '21 at 17:53

1 Answers1

0

The problem was returning (1 << count) would overflow and you need to cast it as said in the comments. So

return (1ULL << count);

fixes it.

YosefAhab
  • 64
  • 10