There is a lot of information on how to find the next power of 2 of a given value (see refs) but I cannot find any to get the previous power of two.
The only way I find so far is to keep a table with all power of two up to 2^64 and make a simple lookup.
This is my current solution to find the next and previous powers of two of any given positive integer n and also a small function to determine if a number is power of two.
This implementation is for Ruby.
class Integer
def power_of_two?
(self & (self - 1) == 0)
end
def next_power_of_two
return 1 if self <= 0
val = self
val = val - 1
val = (val >> 1) | val
val = (val >> 2) | val
val = (val >> 4) | val
val = (val >> 8) | val
val = (val >> 16) | val
val = (val >> 32) | val if self.class == Bignum
val = val + 1
end
def prev_power_of_two
return 1 if self <= 0
val = self
val = val - 1
val = (val >> 1) | val
val = (val >> 2) | val
val = (val >> 4) | val
val = (val >> 8) | val
val = (val >> 16) | val
val = (val >> 32) | val if self.class == Bignum
val = val - (val >> 1)
end
end
Example use:
10.power_of_two? => false
16.power_of_two? => true
10.next_power_of_two => 16
10.prev_power_of_two => 8
For the previous power of two, finding the next and dividing by two is slightly slower than the method above.
I am not sure how it works with Bignums.
From Hacker's Delight, a nice branchless solution:
uint32_t flp2 (uint32_t x)
{
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
return x - (x >> 1);
}
This typically takes 12 instructions. You can do it in fewer if your CPU has a "count leading zeroes" instruction.
bsr solution for AMD CPUs, 3-4x faster for 32-bit version and 1.5-2x for 64-bit version. I've heard it's the opposite for Intel but I do not have access to their CPUs to test. –
Neace x--; as the first line. –
Catty bsr was disastrously slow, like 28 uops with 10c latency and throughput. On K10 and Bulldozer, it's 7 uops with 3 or 4c throughput and latency. About the same on Zen 1 through 3, but single-uop with 0.25c throughput on Zen 4, 1c latency! (uops.info). Intel has fast bsr and fast lzcnt. lzcnt is fast on all AMD CPUs that have it, though, even faster than on Intel. So if you're compiling with -march=x86-64-v3 (AVX2+FMA+BMI2), you can count on fast std::countl_zero –
Grassquit x=0 return 2147483648, which might be less desirable. Or won't matter if your use-case never has zeros as inputs. or if the current behaviour is what you want, just name it something that doesn't include "previous power of 2". –
Grassquit uint32_t previous_power_of_two( uint32_t x ) {
if (x == 0) {
return 0;
}
// x--; Uncomment this, if you want a strictly less than 'x' result.
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return x - (x >> 1);
}
Thanks for the responses. I will try to sum them up and explain a little bit clearer. What this algorithm does is changing to 'ones' all bits after the first 'one' bit, cause these are the only bits that can make our 'x' larger than its previous power of two. After making sure they are 'ones', it just removes them, leaving the first 'one' bit intact. That single bit in its place is our previous power of two.
Here is a one liner for posterity (ruby):
2**Math.log(input, 2).floor(0)
log implementation guarantee that the result is exact for powers of two? If not, it could be slightly below the exact result so floor rounds all the way down. I wouldn't use FP math for this, at least not math library functions that aren't required by IEEE-754 to produce correctly-rounded results. –
Grassquit Math.log(input, 2) avoids conversion to natural-log and back, it might be safe. The usual implementation strategy for log is to extract the exponent field from the bit-pattern and add the result of a polynomial over the mantissa. (This is the part you want floor to discard. Using int to FP conversion and just extracting the exponent field from the FP bit-pattern (after type-punning it back to integer) is a known way to find the position of the leading 1 bit.) If the polynomial approximation is exactly 0 for a mantissa of 0 (representing 1.0), and doesn't go negative for small pos... –
Grassquit The g++ compiler provides a builtin function __builtin_clz that counts leading zeros:
So we could do:
int previousPowerOfTwo(unsigned int x) {
return 1 << (sizeof(x)*8 - 1) - __builtin_clz(x);
}
int main () {
std::cout << previousPowerOfTwo(7) << std::endl;
std::cout << previousPowerOfTwo(31) << std::endl;
std::cout << previousPowerOfTwo(33) << std::endl;
std::cout << previousPowerOfTwo(8) << std::endl;
std::cout << previousPowerOfTwo(91) << std::endl;
return 0;
}
Results:
4
16
32
8
64
But note that, for x == 0, __builtin_clz return is undefined.
std::countl_zero from #include <bit>, which is well-defined for input=0, producing the bit-width of the input. e.g. 32 for uint32_t. So it's slightly slower than __builtin_clz on older x86 where it has to check for zero around using bsr, but full-speed if it can compile to lzcnt which has the same semantics for input = 0. –
Grassquit round_down_to_pow2, not always the previous. –
Grassquit unsigned. It makes more sense to return unsigned 2147483648 than int -2147483648 for an input of UINT_MAX. I was playing around with some versions that use std::numeric_limits<T>::digits instead of assuming CHAR_BIT=8 and not padding, as well as being safe for all inputs, or not since that can be slower. godbolt.org/z/Mrs38vPr3 –
Grassquit std::bit_floor which does the whole thing (and returns 0 for input=0). en.cppreference.com/w/cpp/numeric/bit_floor . libstdc++'s implementation isn't as efficient as mine, at least on x86 when lzcnt is available. libc++'s compiles well with clang: godbolt.org/z/drK9KE7sf –
Grassquit Probably the simplest approach (for positive numbers):
// find next (must be greater) power, and go one back
p = 1; while (p <= n) p <<= 1; p >>= 1;
You can make variations in many ways if you want to optimize.
n = UINT_MAX, there is no unsigned p such that p <= n is false, let alone a power of 2. You could check for p <= (n>>1), because n>>1 has an MSB of 0 (after a logical right shift.) –
Grassquit If you can get the next-higher power of 2, the next-lower power of 2 is either that next-higher or half that. It depends on what you consider to be the "next higher" for any power of 2 (and what you consider to be the next-lower power of 2).
What about
if (tt = v >> 16)
{
r = (t = tt >> 8) ? 0x1000000 * Table256[t] : 0x10000 * Table256[tt];
}
else
{
r = (t = v >> 8) ? 0x100 * Table256[t] : Table256[v];
}
It is just modified method from http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup. This require like 7 operations and it might be faster to replace multiplications whit shift.
Solution with bit manipulation only:
long FindLargestPowerOf2LowerThanN(long n)
{
Assert.IsTrue(n > 0);
byte digits = 0;
while (n > 0)
{
n >>= 1;
digits++;
}
return 1 << (digits - 1);
}
Example:
FindLargestPowerOf2LowerThanN(6):
Our Goal is to get 4 or 100
1) 6 is 110
2) 110 has 3 digits
3) Since we need to find the largest power of 2 lower than n we subtract 1 from digits
4) 1 << 2 is equal to 100
FindLargestPowerOf2LowerThanN(132):
Our Goal is to get 128 or 10000000
1) 6 is 10000100
2) 10000100 has 8 digits
3) Since we need to find the largest power of 2 lower than n we subtract 1 from digits
4) 1 << 7 is equal to 10000000
For C language, the stdc_bit_floor() series of APIs would be introduced in the C23 standard. There are a type-generic version (stdc_bit_floor() macro) and type-specific versions (stdc_bit_floor_*()) defined in the header <stdbit.h>. In the near future this will be the standard way to round integers to a power of 2.
The latest draft of the C23 standard (N3096)
For C++, C++20 has std::bit_floor which does the exact same thing.
Both stdc_bit_floor(x) and std::bit_floor(x) are required to return 0 if the input value x is zero.
If your compiler and C library do not support C23 yet, here is an implementation that I consider it an "ultimate" solution. I intended the library writers to copy this code and adapt appropriately.
The following code
is targeted for C language (not C++),
uses compiler built-ins to yield efficient code (CLZ or BSR instruction) if compiler supports any,
is portable (standard C and no assembly) with the exception of built-ins, and
addresses undefined behavior of the compiler built-ins (when x is zero).
#include <limits.h>
#ifdef _MSC_VER
# if _MSC_VER >= 1400
/* _BitScanReverse is introduced in Visual C++ 2005 and requires
<intrin.h> (also introduced in Visual C++ 2005). */
#include <intrin.h>
#pragma intrinsic(_BitScanReverse)
#pragma intrinsic(_BitScanReverse64)
# define HAVE_BITSCANREVERSE 1
# endif
#endif
/* Macro indicating that the compiler supports __builtin_clz().
The name HAVE_BUILTIN_CLZ seems to be the most common, but in some
projects HAVE__BUILTIN_CLZ is used instead. */
#ifdef __has_builtin
# if __has_builtin(__builtin_clz)
# define HAVE_BUILTIN_CLZ 1
# endif
#elif defined(__GNUC__)
# if (__GNUC__ > 3)
# define HAVE_BUILTIN_CLZ 1
# elif defined(__GNUC_MINOR__)
# if (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
# define HAVE_BUILTIN_CLZ 1
# endif
# endif
#endif
unsigned int stdc_bit_floor_ui(unsigned int x);
unsigned long stdc_bit_floor_ul(unsigned long x);
unsigned long long stdc_bit_floor_ull(unsigned long long x);
/**
* Returns the largest power of two that is not greater than x. If x
* is 0, returns 0.
*/
unsigned int stdc_bit_floor_ui(unsigned int x)
{
#ifdef HAVE_BITSCANREVERSE
if (x <= 0) {
return 0;
} else {
unsigned long int index;
(void) _BitScanReverse(&index, x);
return (1U << index);
}
#elif defined(HAVE_BUILTIN_CLZ)
if (x <= 0) {
return 0;
}
return (1U << (sizeof(x) * CHAR_BIT - 1 - __builtin_clz(x)));
#else
/* Fastest known solution without compiler built-ins or integer
logarithm instructions.
From the book "Hacker's Delight".
Converted to a loop for smaller code size.
("gcc -O3" will unroll this.) */
{
unsigned int shift;
for (shift = 1; shift < sizeof(x) * CHAR_BIT; shift <<= 1) {
x |= (x >> shift);
}
}
return (x - (x >> 1));
#endif
}
/**
* Returns the largest power of two that is not greater than x. If x
* is 0, returns 0.
*/
unsigned long stdc_bit_floor_ul(unsigned long x)
{
#ifdef HAVE_BITSCANREVERSE
if (x <= 0) {
return 0;
} else {
unsigned long index;
(void) _BitScanReverse(&index, x);
return (1UL << index);
}
#elif defined(HAVE_BUILTIN_CLZ)
if (x <= 0) {
return 0;
}
return (1UL << (sizeof(x) * CHAR_BIT - 1 - __builtin_clzl(x)));
#else
{
unsigned int shift;
for (shift = 1; shift < sizeof(x) * CHAR_BIT; shift <<= 1) {
x |= (x >> shift);
}
}
return (x - (x >> 1));
#endif
}
/**
* Returns the largest power of two that is not greater than x. If x
* is 0, returns 0.
*/
unsigned long long stdc_bit_floor_ull(unsigned long long x)
{
#if (defined(HAVE_BITSCANREVERSE) && \
ULLONG_MAX == 18446744073709551615ULL)
if (x <= 0) {
return 0;
} else {
/* assert(sizeof(__int64) == sizeof(long long)); */
unsigned long int index;
(void) _BitScanReverse64(&index, x);
return (1ULL << index);
}
#elif defined(HAVE_BUILTIN_CLZ)
if (x <= 0) {
return 0;
}
return (1ULL << (sizeof(x) * CHAR_BIT - 1 - __builtin_clzll(x)));
#else
{
unsigned int shift;
for (shift = 1; shift < sizeof(x) * CHAR_BIT; shift <<= 1) {
x |= (x >> shift);
}
}
return (x - (x >> 1));
#endif
}
Using a count leading zeros function (a.k.a. bitscan right), determining the next lowest power of 2 is easy:
uint32_t lower_power_of_2(uint32_t x) {
assert(x != 0);
return 1 << (31 - __builtin_clz(x));
}
Here, __builtin_clz is recognized by gcc and clang. Use _BitScanReverse with a Microsoft compiler.
This is my way:
//n is the number you want to find the previus power of 2
long m = 1;
while(n > 1){
n >>= 1;
m <<= 1;
}
//m is the previous power of two
Starting with C++20 the simple and portable solution is std::bit_floor.
If
xis not zero, calculates the largest integral power of two that is not greater thanx. Ifxis zero, returns zero.
At this point, Microsoft's STL, libc++, and libstdc++ all provide optimized implementations of std::bit_floor based on std::countl_zero, so this is likely to give you optimal codegen.
This can be done in one line.
int nextLowerPowerOf2 = i <= 0
? 0
: ((i & (~i + 1)) == i)
? i >> 1
: (1 << (int)Math.Log(i, 2));
result
i power_of_2
-2 0
-1 0
0 0
1 0
2 1
3 2
4 2
5 4
6 4
7 4
8 4
9 8
Here's a more readable version in c#, with the <=0 guard clause distributed to the utility methods.
int nextLowerPowerOf2 = IsPowerOfTwo(i)
? i >> 1 // shift it right
: GetPowerOfTwoLessThanOrEqualTo(i);
public static int GetPowerOfTwoLessThanOrEqualTo(int x)
{
return (x <= 0 ? 0 : (1 << (int)Math.Log(x, 2)));
}
public static bool IsPowerOfTwo(int x)
{
return (((x & (~x + 1)) == x) && (x > 0));
}
When you work in base 2, you can jump from a power of two to the next one by just adding or removing a digit from the right.
For instance, the previous power of two of the number 8 is the number 4. In binary:
01000 -> 0100 (we remove the trailing zero to get number 4)
So the algorithm to solve the calculus of the previous power of two is:
previousPower := number shr 1
previousPower = number >> 1
(or any other syntax)
number is also a power of 2. If number is say 11, then this wont work. –
Wildfowl Below code will find the previous power of 2:
int n = 100;
n /= 2;//commenting this will gives the next power of 2
n |= n>>1;
n |= n>>2;
n |= n>>4;
n |= n>>16;
System.out.println(n+1);
This is my current solution to find the next and previous powers of two of any given positive integer n and also a small function to determine if a number is power of two.
This implementation is for Ruby.
class Integer
def power_of_two?
(self & (self - 1) == 0)
end
def next_power_of_two
return 1 if self <= 0
val = self
val = val - 1
val = (val >> 1) | val
val = (val >> 2) | val
val = (val >> 4) | val
val = (val >> 8) | val
val = (val >> 16) | val
val = (val >> 32) | val if self.class == Bignum
val = val + 1
end
def prev_power_of_two
return 1 if self <= 0
val = self
val = val - 1
val = (val >> 1) | val
val = (val >> 2) | val
val = (val >> 4) | val
val = (val >> 8) | val
val = (val >> 16) | val
val = (val >> 32) | val if self.class == Bignum
val = val - (val >> 1)
end
end
Example use:
10.power_of_two? => false
16.power_of_two? => true
10.next_power_of_two => 16
10.prev_power_of_two => 8
For the previous power of two, finding the next and dividing by two is slightly slower than the method above.
I am not sure how it works with Bignums.
© 2022 - 2024 — McMap. All rights reserved.