2의 다음 곱셈까지 반올림
가장 가까운 2의 거듭제곱을 반환하는 함수를 쓰고 싶습니다.예를 들어 입력이 789일 경우 출력은 1024가 됩니다.루프를 사용하지 않고 일부 비트 연산자를 사용하여 이를 실현하는 방법이 있습니까?
Bit Twiddling Hacks를 확인합니다.밑수 2의 대수를 구해야 하고 거기에 1을 더해야 합니다.32비트 값의 예:
다음으로 높은 2의 곱으로 반올림
unsigned int v; // compute the next highest power of 2 of 32-bit v v--; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v++;
다른 폭에 대한 확장은 분명해야 한다.
이것도 효과가 있을 것 같아요.
int power = 1;
while(power < x)
power*=2;
그리고 정답은power.
next = pow(2, ceil(log(x)/log(2)));
이것은 x를 얻기 위해 2로 올리는 숫자를 찾는 것으로 동작합니다(숫자의 로그를 가져다가 원하는 베이스의 로그로 나누면 자세한 것은 위키피디아를 참조).그런 다음 가장 가까운 정수 거듭제곱을 얻으려면 ceil로 반올림하세요.
이것은 다른 곳에 링크되어 있는 비트 방식보다 더 일반적인 목적(느리다는 것!)이지만, 수학을 아는 것이 좋습니다.
표준으로c++20이것은 에 포함되어 있습니다.<bit>답은 간단하다.
#include <bit>
unsigned long upper_power_of_two(unsigned long v)
{
return std::bit_ceil(v);
}
메모: 제가 제시한 솔루션은c++,것은 아니다.c대신 이 질문에 대답하고 싶지만, 이 질문의 중복으로 종료되었습니다!
GCC를 사용하는 경우 Lockless Inc.의 Optimizing the next_pow2() 함수를 참조해 주십시오.이 페이지에서는 내장 함수를 사용하는 방법을 설명합니다.builtin_clz()(0에 선행하는 카운트) 이후 직접 x86(ia32) 어셈블러 명령을 사용합니다.bsr(비트 스캔 리버스)는, 다른 회답의 gamedev 사이트에의 링크에 기재되어 있는 것과 같습니다.이 코드는 이전 답변에서 설명한 것보다 더 빠를 수 있습니다.
덧붙여서, 어셈블러 명령과 64비트 데이터 타입을 사용하지 않을 경우, 이것을 사용할 수 있습니다.
/**
* return the smallest power of two value
* greater than x
*
* Input range: [2..2147483648]
* Output range: [2..2147483648]
*
*/
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
assert(x > 1);
assert(x <= ((UINT32_MAX/2) + 1));
#endif
return 1 << (32 - __builtin_clz (x - 1));
}
하나 더, 비록 사이클을 사용하지만, 수학 연산자보다 훨씬 빠릅니다.
두 가지 "바닥" 옵션의 검정력:
int power = 1;
while (x >>= 1) power <<= 1;
두 가지 "최소" 옵션 중 하나:
int power = 2;
x--; // <<-- UPDATED
while (x >>= 1) power <<= 1;
갱신하다
댓글에서 언급했듯이 에 실수가 있었다.ceil결과가 잘못된 곳이죠
풀기능은 다음과 같습니다.
unsigned power_floor(unsigned x) {
int power = 1;
while (x >>= 1) power <<= 1;
return power;
}
unsigned power_ceil(unsigned x) {
if (x <= 1) return 1;
int power = 2;
x--;
while (x >>= 1) power <<= 1;
return power;
}
질문에도 불구하고c여기 내 5센트요.다행히 C++ 20에는std::ceil2그리고.std::floor2(여기를 참조).그렇다.consexpr템플릿 함수, 현재 GCC 구현에서는 비트시프트가 사용되며 모든 일체형 부호 없는 유형으로 동작합니다.
x86에서는 sse4 비트 조작 명령을 사용하여 고속화할 수 있습니다.
//assume input is in eax
mov ecx,31
popcnt edx,eax //cycle 1
lzcnt eax,eax //cycle 2
sub ecx,eax
mov eax,1
cmp edx,1 //cycle 3
jle @done //cycle 4 - popcnt says its a power of 2, return input unchanged
shl eax,cl //cycle 5
@done: rep ret //cycle 5
c에서는 일치하는 함수를 사용할 수 있습니다.
또는 점프를 통한 오심을 방지하여 속도를 높이고 종속성 체인을 연장하여 속도를 늦춥니다.어떤 것이 가장 적합한지 코드 시간을 재보세요.
//assume input is in eax
mov ecx,31
popcnt edx,eax //cycle 1
lzcnt eax,eax
sub ecx,eax
mov eax,1 //cycle 2
cmp edx,1
mov edx,0 //cycle 3
cmovle ecx,edx //cycle 4 - ensure eax does not change
shl eax,cl
@done: rep ret //cycle 5
여기 C의 솔루션이 있습니다.이게 도움이 됐으면 좋겠네요!
int next_power_of_two(int n) {
int i = 0;
for (--n; n > 0; n >>= 1) {
i++;
}
return 1 << i;
}
부호 없는 타입의 경우 비트트위들링 해크를 기반으로 구축:
#include <climits>
#include <type_traits>
template <typename UnsignedType>
UnsignedType round_up_to_power_of_2(UnsignedType v) {
static_assert(std::is_unsigned<UnsignedType>::value, "Only works for unsigned types");
v--;
for (size_t i = 1; i < sizeof(v) * CHAR_BIT; i *= 2) //Prefer size_t "Warning comparison between signed and unsigned integer"
{
v |= v >> i;
}
return ++v;
}
컴파일러는 컴파일 시에 반복 횟수를 알 수 있기 때문에 루프는 없습니다.
unsigned long upper_power_of_two(unsigned long v)
{
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
return v;
}
constexpr 버전의 c++14용 clp2
#include <iostream>
#include <type_traits>
// Closest least power of 2 minus 1. Returns 0 if n = 0.
template <typename UInt, std::enable_if_t<std::is_unsigned<UInt>::value,int> = 0>
constexpr UInt clp2m1(UInt n, unsigned i = 1) noexcept
{ return i < sizeof(UInt) * 8 ? clp2m1(UInt(n | (n >> i)),i << 1) : n; }
/// Closest least power of 2 minus 1. Returns 0 if n <= 0.
template <typename Int, std::enable_if_t<std::is_integral<Int>::value && std::is_signed<Int>::value,int> = 0>
constexpr auto clp2m1(Int n) noexcept
{ return clp2m1(std::make_unsigned_t<Int>(n <= 0 ? 0 : n)); }
/// Closest least power of 2. Returns 2^N: 2^(N-1) < n <= 2^N. Returns 0 if n <= 0.
template <typename Int, std::enable_if_t<std::is_integral<Int>::value,int> = 0>
constexpr auto clp2(Int n) noexcept
{ return clp2m1(std::make_unsigned_t<Int>(n-1)) + 1; }
/// Next power of 2. Returns 2^N: 2^(N-1) <= n < 2^N. Returns 1 if n = 0. Returns 0 if n < 0.
template <typename Int, std::enable_if_t<std::is_integral<Int>::value,int> = 0>
constexpr auto np2(Int n) noexcept
{ return clp2m1(std::make_unsigned_t<Int>(n)) + 1; }
template <typename T>
void test(T v) { std::cout << clp2(v) << std::endl; }
int main()
{
test(-5); // 0
test(0); // 0
test(8); // 8
test(31); // 32
test(33); // 64
test(789); // 1024
test(char(260)); // 4
test(unsigned(-1) - 1); // 0
test<long long>(unsigned(-1) - 1); // 4294967296
return 0;
}
다음과 같은 설명이 목적에 도움이 될 수 있습니다.
이를 위한 "최종" 솔루션을 만들려고 합니다.다음 코드
(C++가 아닌) C 언어를 대상으로 합니다.
컴파일러가 지원하는 경우 컴파일러 빌트인을 사용하여 효율적인 코드(CLZ 또는 BSR 명령)를 생성합니다.
(표준 C 및 조립품 없음)는 내장되어 있는 것을 제외하고, 휴대성이 있습니다.
는 정의되지 않은 모든 동작을 처리합니다.
C++로 쓸 경우 코드를 적절히 조정할 수 있습니다.C++20 에는 std::bit_ceil 이 도입되어 있습니다.단, 동작은 특정 조건에서 정의되지 않을 수 있습니다.
#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
/**
* Returns the smallest power of two that is not smaller than x.
*/
unsigned long int next_power_of_2_long(unsigned long int x)
{
if (x <= 1) {
return 1;
}
x--;
#ifdef HAVE_BITSCANREVERSE
if (x > (ULONG_MAX >> 1)) {
return 0;
} else {
unsigned long int index;
(void) _BitScanReverse(&index, x);
return (1UL << (index + 1));
}
#elif defined(HAVE_BUILTIN_CLZ)
if (x > (ULONG_MAX >> 1)) {
return 0;
}
return (1UL << (sizeof(x) * CHAR_BIT - __builtin_clzl(x)));
#else
/* Solution from "Bit Twiddling Hacks"
<http://www.graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2>
but 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 + 1);
#endif
}
unsigned int next_power_of_2(unsigned int x)
{
if (x <= 1) {
return 1;
}
x--;
#ifdef HAVE_BITSCANREVERSE
if (x > (UINT_MAX >> 1)) {
return 0;
} else {
unsigned long int index;
(void) _BitScanReverse(&index, x);
return (1U << (index + 1));
}
#elif defined(HAVE_BUILTIN_CLZ)
if (x > (UINT_MAX >> 1)) {
return 0;
}
return (1U << (sizeof(x) * CHAR_BIT - __builtin_clz(x)));
#else
{
unsigned int shift;
for (shift = 1; shift < sizeof(x) * CHAR_BIT; shift <<= 1) {
x |= (x >> shift);
}
}
return (x + 1);
#endif
}
unsigned long long next_power_of_2_long_long(unsigned long long x)
{
if (x <= 1) {
return 1;
}
x--;
#if (defined(HAVE_BITSCANREVERSE) && \
ULLONG_MAX == 18446744073709551615ULL)
if (x > (ULLONG_MAX >> 1)) {
return 0;
} else {
/* assert(sizeof(__int64) == sizeof(long long)); */
unsigned long int index;
(void) _BitScanReverse64(&index, x);
return (1ULL << (index + 1));
}
#elif defined(HAVE_BUILTIN_CLZ)
if (x > (ULLONG_MAX >> 1)) {
return 0;
}
return (1ULL << (sizeof(x) * CHAR_BIT - __builtin_clzll(x)));
#else
{
unsigned int shift;
for (shift = 1; shift < sizeof(x) * CHAR_BIT; shift <<= 1) {
x |= (x >> shift);
}
}
return (x + 1);
#endif
}
정수 입력을 위한 C/C++의 효율적인 Microsoft(예: Visual Studio 2017) 전용 솔루션.최상위 1비트의 위치를 확인하기 전에 감소하여 2개의 값의 거듭제곱과 정확히 일치하는 입력의 경우를 처리합니다.
inline unsigned int ExpandToPowerOf2(unsigned int Value)
{
unsigned long Index;
_BitScanReverse(&Index, Value - 1);
return (1U << (Index + 1));
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#if defined(WIN64) // The _BitScanReverse64 intrinsic is only available for 64 bit builds because it depends on x64
inline unsigned long long ExpandToPowerOf2(unsigned long long Value)
{
unsigned long Index;
_BitScanReverse64(&Index, Value - 1);
return (1ULL << (Index + 1));
}
#endif
이것에 의해, 다음과 같은 인텔·프로세서에 대해서, 5개 정도의 순서가 작성됩니다.
dec eax
bsr rcx, rax
inc ecx
mov eax, 1
shl rax, cl
Visual Studio C++ 컴파일러는 컴파일 시간 값을 최적화하도록 코드화되어 있지 않지만 명령어가 많이 있는 것은 아닙니다.
편집:
입력값 1을 1로 하는 경우(2의 0제곱) 위의 코드를 조금만 수정해도 분기가 없는 명령어가 그대로 생성됩니다.
inline unsigned int ExpandToPowerOf2(unsigned int Value)
{
unsigned long Index;
_BitScanReverse(&Index, --Value);
if (Value == 0)
Index = (unsigned long) -1;
return (1U << (Index + 1));
}
몇 가지 명령만 더 생성합니다.문제는 Index가 테스트에 이어 cmove 명령으로 대체될 수 있다는 것입니다.
IEEE 플로트의 경우는, 다음과 같은 조작이 가능합니다.
int next_power_of_two(float a_F){
int f = *(int*)&a_F;
int b = f << 9 != 0; // If we're a power of two this is 0, otherwise this is 1
f >>= 23; // remove factional part of floating point number
f -= 127; // subtract 127 (the bias) from the exponent
// adds one to the exponent if were not a power of two,
// then raises our new exponent to the power of two again.
return (1 << (f + b));
}
정수 솔루션이 필요하고 인라인 어셈블리를 사용할 수 있는 경우 BSR은 x86의 정수 log2를 제공합니다.설정되어 있는 오른쪽 비트의 수를 카운트 합니다.이것은, 그 숫자의 log2와 정확하게 같습니다.CLZ 등 다른 프로세서에도 유사한 명령어가 있습니다(대부분). 컴파일러에 따라서는 작업을 수행할 수 있는 내재가 있을 수 있습니다.
C#의 휴대용 솔루션:
int GetNextPowerOfTwo(int input) {
return 1 << (int)Math.Ceiling(Math.Log2(input));
}
Math.Ceiling(Math.Log2(value))2의 인 2의 합니다.1 <<는 비트 시프트를 통해 실제 값을 계산합니다.
가 있는 경우 더 빠른 솔루션.NET Core 3 이상:
uint GetNextPowerOfTwoFaster(uint input) {
return (uint)1 << (sizeof(uint) * 8 - System.Numerics.BitOperations.LeadingZeroCount(input - 1));
}
은 「」를 사용합니다.System.Numerics.BitOperations.LeadingZeroCount()사용 가능한 경우 하드웨어 명령을 사용합니다.
업데이트:
RoundUpToPowerOf2()가 착신 중입니다.NET 6! 내부 실장은 와 거의 동일합니다.위의 NET Core 3 솔루션
지역사회의 최신 소식입니다.
/*
** http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
*/
#define __LOG2A(s) ((s &0xffffffff00000000) ? (32 +__LOG2B(s >>32)): (__LOG2B(s)))
#define __LOG2B(s) ((s &0xffff0000) ? (16 +__LOG2C(s >>16)): (__LOG2C(s)))
#define __LOG2C(s) ((s &0xff00) ? (8 +__LOG2D(s >>8)) : (__LOG2D(s)))
#define __LOG2D(s) ((s &0xf0) ? (4 +__LOG2E(s >>4)) : (__LOG2E(s)))
#define __LOG2E(s) ((s &0xc) ? (2 +__LOG2F(s >>2)) : (__LOG2F(s)))
#define __LOG2F(s) ((s &0x2) ? (1) : (0))
#define LOG2_UINT64 __LOG2A
#define LOG2_UINT32 __LOG2B
#define LOG2_UINT16 __LOG2C
#define LOG2_UINT8 __LOG2D
static inline uint64_t
next_power_of_2(uint64_t i)
{
#if defined(__GNUC__)
return 1UL <<(1 +(63 -__builtin_clzl(i -1)));
#else
i =i -1;
i =LOG2_UINT64(i);
return 1UL <<(1 +i);
#endif
}
정의되지 않은 동작의 영역에 들어가지 않으려면 입력 값이 1 ~2^63 사이여야 합니다.이 매크로는 컴파일 시 상수를 설정할 때도 유용합니다.
Excel에 대한 Paul Dixon의 답변은 완벽하게 작동합니다.
=POWER(2,CEILING.MATH(LOG(A1)/LOG(2)))
는 ""를 지원합니다.log base 2 매우 한 조작– " " " " 。count leading zeros. 많은 컴파일러가 이 기능을 내장하고 있습니다.https://en.wikipedia.org/wiki/Find_first_set 를 참조해 주세요.
완전성을 위해 여기에서는 bog-standard C에서의 부동소수점 실장을 실시합니다.
double next_power_of_two(double value) {
int exp;
if(frexp(value, &exp) == 0.5) {
// Omit this case to round precise powers of two up to the *next* power
return value;
}
return ldexp(1.0, exp);
}
float로 변환한 후 정규화된 IEEE 표현을 나타내는 .hex()를 사용합니다.
>>> float(789).hex() '0x1.8a80000000000p+9'
그리고 지수를 추출하고 1을 더하면 됩니다.
>>> int(float(789).hex().split('p+')[1]) + 1 10
그리고 2를 이 제곱으로 올립니다.
>>> 2 ** (int(float(789).hex().split('p+')[1]) + 1) 1024
한 줄 템플릿이 필요한 경우.여기 있어요.
int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>1)>>2)>>4)>>8)>>16); }
또는
int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>(1<<0))>>(1<<1))>>(1<<2))>>(1<<3))>>(1<<4)); }
import sys
def is_power2(x):
return x > 0 and ((x & (x - 1)) == 0)
def find_nearest_power2(x):
if x <= 0:
raise ValueError("invalid input")
if is_power2(x):
return x
else:
bits = get_bits(x)
upper = 1 << (bits)
lower = 1 << (bits - 1)
mid = (upper + lower) // 2
if (x - mid) > 0:
return upper
else:
return lower
def get_bits(x):
"""return number of bits in binary representation"""
if x < 0:
raise ValueError("invalid input: input should be positive integer")
count = 0
while (x != 0):
try:
x = x >> 1
except TypeError as error:
print(error, "input should be of type integer")
sys.exit(1)
count += 1
return count
from math import ceil, log2
pot_ceil = lambda N: 0x1 << ceil(log2(N))
테스트:
for i in range(10):
print(i, pot_ceil(i))
출력:
1 1
2 2
3 4
4 4
5 8
6 8
7 8
8 8
9 16
10 16
당신이 좋은 컴파일러를 가지고 있고, 이 시점에서 나보다 먼저 손을 놀릴 수 있다고 가정한다면, 어쨌든 이것은 효과가 있습니다!!!
// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
#define SH1(v) ((v-1) | ((v-1) >> 1)) // accidently came up w/ this...
#define SH2(v) ((v) | ((v) >> 2))
#define SH4(v) ((v) | ((v) >> 4))
#define SH8(v) ((v) | ((v) >> 8))
#define SH16(v) ((v) | ((v) >> 16))
#define OP(v) (SH16(SH8(SH4(SH2(SH1(v))))))
#define CB0(v) ((v) - (((v) >> 1) & 0x55555555))
#define CB1(v) (((v) & 0x33333333) + (((v) >> 2) & 0x33333333))
#define CB2(v) ((((v) + ((v) >> 4) & 0xF0F0F0F) * 0x1010101) >> 24)
#define CBSET(v) (CB2(CB1(CB0((v)))))
#define FLOG2(v) (CBSET(OP(v)))
아래 테스트 코드:
#include <iostream>
using namespace std;
// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
#define SH1(v) ((v-1) | ((v-1) >> 1)) // accidently guess this...
#define SH2(v) ((v) | ((v) >> 2))
#define SH4(v) ((v) | ((v) >> 4))
#define SH8(v) ((v) | ((v) >> 8))
#define SH16(v) ((v) | ((v) >> 16))
#define OP(v) (SH16(SH8(SH4(SH2(SH1(v))))))
#define CB0(v) ((v) - (((v) >> 1) & 0x55555555))
#define CB1(v) (((v) & 0x33333333) + (((v) >> 2) & 0x33333333))
#define CB2(v) ((((v) + ((v) >> 4) & 0xF0F0F0F) * 0x1010101) >> 24)
#define CBSET(v) (CB2(CB1(CB0((v)))))
#define FLOG2(v) (CBSET(OP(v)))
#define SZ4 FLOG2(4)
#define SZ6 FLOG2(6)
#define SZ7 FLOG2(7)
#define SZ8 FLOG2(8)
#define SZ9 FLOG2(9)
#define SZ16 FLOG2(16)
#define SZ17 FLOG2(17)
#define SZ127 FLOG2(127)
#define SZ1023 FLOG2(1023)
#define SZ1024 FLOG2(1024)
#define SZ2_17 FLOG2((1ul << 17)) //
#define SZ_LOG2 FLOG2(SZ)
#define DBG_PRINT(x) do { std::printf("Line:%-4d" " %10s = %-10d\n", __LINE__, #x, x); } while(0);
uint32_t arrTble[FLOG2(63)];
int main(){
int8_t n;
DBG_PRINT(SZ4);
DBG_PRINT(SZ6);
DBG_PRINT(SZ7);
DBG_PRINT(SZ8);
DBG_PRINT(SZ9);
DBG_PRINT(SZ16);
DBG_PRINT(SZ17);
DBG_PRINT(SZ127);
DBG_PRINT(SZ1023);
DBG_PRINT(SZ1024);
DBG_PRINT(SZ2_17);
return(0);
}
출력:
Line:39 SZ4 = 2
Line:40 SZ6 = 3
Line:41 SZ7 = 3
Line:42 SZ8 = 3
Line:43 SZ9 = 4
Line:44 SZ16 = 4
Line:45 SZ17 = 5
Line:46 SZ127 = 7
Line:47 SZ1023 = 10
Line:48 SZ1024 = 10
Line:49 SZ2_16 = 17
나는 가장 낮은 2의 힘을 얻으려고 노력하고 이 기능을 만들었다.도움이 되길.2의 최대 제곱을 얻기 위해 가장 가까운 작은 숫자에 2를 곱했습니다.
int nearest_upper_power(int number){
int temp=number;
while((number&(number-1))!=0){
temp<<=1;
number&=temp;
}
//Here number is closest lower power
number*=2;
return number;
}
@YanDroneaud에 한 @.x==1 또는만:x86 "", "", "gcc "clang":
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
assert(x > 0);
assert(x <= ((UINT32_MAX/2) + 1));
#endif
int clz;
uint32_t xm1 = x-1;
asm(
"lzcnt %1,%0"
:"=r" (clz)
:"rm" (xm1)
:"cc"
);
return 1 << (32 - clz);
}
입력이 상수 표현일 경우, 이것을 상수 표현으로 만들기 위해 사용하고 있습니다.
#define uptopow2_0(v) ((v) - 1)
#define uptopow2_1(v) (uptopow2_0(v) | uptopow2_0(v) >> 1)
#define uptopow2_2(v) (uptopow2_1(v) | uptopow2_1(v) >> 2)
#define uptopow2_3(v) (uptopow2_2(v) | uptopow2_2(v) >> 4)
#define uptopow2_4(v) (uptopow2_3(v) | uptopow2_3(v) >> 8)
#define uptopow2_5(v) (uptopow2_4(v) | uptopow2_4(v) >> 16)
#define uptopow2(v) (uptopow2_5(v) + 1) /* this is the one programmer uses */
예를 들어 다음과 같은 표현입니다.
uptopow2(sizeof (struct foo))
상수로 잘 감소합니다.
g++ 컴파일러는 선행 0을 카운트하는 빌트인 함수 __builtin_clz를 제공합니다.
다음과 같은 작업을 할 수 있습니다.
int nextPowerOfTwo(unsigned int x) {
return 1 << sizeof(x)*8 - __builtin_clz(x);
}
int main () {
std::cout << nextPowerOfTwo(7) << std::endl;
std::cout << nextPowerOfTwo(31) << std::endl;
std::cout << nextPowerOfTwo(33) << std::endl;
std::cout << nextPowerOfTwo(8) << std::endl;
std::cout << nextPowerOfTwo(91) << std::endl;
return 0;
}
결과:
8
32
64
16
128
, ,의 의의 경우 의의 경우 입니다.x == 0,__builtin_clz되지 않았습니다return은 정의되지 않았습니다.
언급URL : https://stackoverflow.com/questions/466204/rounding-up-to-next-power-of-2
'programing' 카테고리의 다른 글
| Visual Studio에서 작동하는 TypeScript용 Vue.js 2.0 타이핑을 가져오려면 어떻게 해야 합니까? (0) | 2022.08.18 |
|---|---|
| GCC C 코드의 비정적 선언 다음에 정적 선언을 해결하려면 어떻게 해야 합니까? (0) | 2022.08.17 |
| $auth.get에 접속하는 방법서비스의 토큰('local')을 선택하십시오. (0) | 2022.08.17 |
| nuxt 사용 시 핫 새로고침을 끌 수 있습니까? (0) | 2022.08.17 |
| Linux에서 C 프로그래밍 언어의 헤더 파일을 찾으려면 어떻게 해야 하나요? (0) | 2022.08.17 |