how to find leftmost 1-bit in C++ ?
in other word I want to find biggest k so that 2^k <= N for some given number N
for example if N=10 then k=3
I want an O(1) time and memory solution and also without using built-in functions that may not compile in ALL C++ compilers.
thank you in advance.
plz tell me this is correct or not ?
------------------------------------------- int highestOneBit(int i) { i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i — (i >> 1); }
__lg(n) will do your work.
without using built-in functions that may not compile in ALL C++ compilers?I think this works for $$$O(log(log(n)))$$$. In order for it to work for $$$O(1)$$$, you need to add:
this blog is copy pasted from here
idk why he didn't even bother using google
__builtin_clz or __builtin_clzll
in other word I want to find biggest k so that 2^k <= N for some given number N
__builtin_clz does almost this. It counts number of leading zeros in binary, so 32 — return value is number of digits in binary representation of a number which is almost what you want to find. Now you need to just correct some off-by-one errors in what I said here.
In C++20 you can use
std::bit_width(x) - 1.