정수가 주어지면 비트 트위들 링을 사용하여 다음으로 큰 2의 거듭 제곱을 어떻게 찾을 수 있습니까?
나는 정수가있는 경우 n, 어떻게 다음 번호를 찾을 수 있습니다 k > n되도록 k = 2^i, 일부 i의 요소 N비트 이동 또는 논리에 의해.
예 : 내가있는 경우 n = 123, k = 1282의 거듭 제곱이고 2 124로만 나눌 수 없는 을 어떻게 찾을 수 있습니까? 이것은 간단해야하지만 나를 피할 수 있습니다.
32 비트 정수의 경우 이는 간단하고 간단한 경로입니다.
unsigned int n;
n--;
n |= n >> 1; // Divide by 2^k for consecutive doublings of k up to 32,
n |= n >> 2; // and then or the results.
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++; // The result is a number of 1 bits equal to the number
// of bits in the original number, plus 1. That's the
// next highest power of 2.
다음은 더 구체적인 예입니다. 이진수로 11011101 인 숫자 221을 봅시다.
n--; // 1101 1101 --> 1101 1100
n |= n >> 1; // 1101 1100 | 0110 1110 = 1111 1110
n |= n >> 2; // 1111 1110 | 0011 1111 = 1111 1111
n |= n >> 4; // ...
n |= n >> 8;
n |= n >> 16; // 1111 1111 | 1111 1111 = 1111 1111
n++; // 1111 1111 --> 1 0000 0000
2 ^ 8 또는 256 을 나타내는 아홉 번째 위치에 1 비트가 있습니다 . 이는 실제로 2의 다음으로 큰 거듭 제곱입니다 . 각 시프트는 숫자의 기존 1 비트를 이전에 변경되지 않은 일부 0과 겹치며 결국 원래 숫자의 비트 수와 동일한 수의 1 비트를 생성합니다. 이 값에 1을 더하면 2의 새로운 거듭 제곱이 생성됩니다.
다른 예시; 바이너리에서 10000011 인 131을 사용합니다.
n--; // 1000 0011 --> 1000 0010
n |= n >> 1; // 1000 0010 | 0100 0001 = 1100 0011
n |= n >> 2; // 1100 0011 | 0011 0000 = 1111 0011
n |= n >> 4; // 1111 0011 | 0000 1111 = 1111 1111
n |= n >> 8; // ... (At this point all bits are 1, so further bitwise-or
n |= n >> 16; // operations produce no effect.)
n++; // 1111 1111 --> 1 0000 0000
그리고 실제로 256은 131에서 2의 다음으로 높은 제곱입니다.
정수를 나타내는 데 사용 된 비트 수가 2의 거듭 제곱 인 경우이 기술을 계속해서 효율적이고 무한하게 확장 할 수 있습니다 (예 : n >> 3264 비트 정수에 대한 행 추가 ).
실제로이를위한 어셈블리 솔루션이 있습니다 (80386 명령 세트 이후).
BSR (Bit Scan Reverse) 명령어를 사용하여 정수에서 최상위 비트를 스캔 할 수 있습니다.
bsr은 더블 워드 피연산자 또는 두 번째 워드에서 최상위 비트부터 시작하여 비트를 스캔합니다. 비트가 모두 0이면 ZF가 지워집니다. 그렇지 않으면 ZF가 설정되고 역방향으로 스캔하는 동안 발견 된 첫 번째 설정 비트의 비트 인덱스가 대상 레지스터에로드됩니다.
(발췌 : http://dlc.sun.com/pdf/802-1948/802-1948.pdf )
그리고 inc보다 1의 결과.
그래서:
bsr ecx, eax //eax = number
jz @zero
mov eax, 2 // result set the second bit (instead of a inc ecx)
shl eax, ecx // and move it ecx times to the left
ret // result is in eax
@zero:
xor eax, eax
ret
최신 CPU에서는 훨씬 빠른 lzcnt명령 (일명 rep bsr)을 사용할 수 있습니다 . lzcnt단일 주기로 작업을 수행합니다.
루프가없는 더 수학적 방법 :
public static int ByLogs(int n)
{
double y = Math.Floor(Math.Log(n, 2));
return (int)Math.Pow(2, y + 1);
}
다음은 논리적 인 대답입니다.
function getK(int n)
{
int k = 1;
while (k < n)
k *= 2;
return k;
}
다음은 Python의 긴 정수를 처리 할 수 있도록 루프로 구현 된 John Feminella의 답변 입니다 .
def next_power_of_2(n):
"""
Return next power of 2 greater than or equal to n
"""
n -= 1 # greater than OR EQUAL TO n
shift = 1
while (n+1) & n: # n+1 is not a power of 2 yet
n |= n >> shift
shift <<= 1
return n + 1
n이 이미 2의 거듭 제곱이면 더 빠르게 반환됩니다.
Python> 2.7의 경우 대부분의 N에서 더 간단하고 빠릅니다.
def next_power_of_2(n):
"""
Return next power of 2 greater than or equal to n
"""
return 2**(n-1).bit_length()
여기에 루프가 없지만 중간 부동 소수점을 사용하는 야생이 있습니다.
// compute k = nextpowerof2(n)
if (n > 1)
{
float f = (float) n;
unsigned int const t = 1U << ((*(unsigned int *)&f >> 23) - 0x7f);
k = t << (t < n);
}
else k = 1;
이것과 John Feminella가 제출 한 내용을 포함하여 다른 많은 해킹 해킹은 여기 에서 찾을 수 있습니다 .
보다 큼 /보다 크거나 같음
다음 스 니펫은 OP에 지정된대로 k = 2 ^ i
(n = 123 => k = 128, n = 128 => k = 256)가되는 다음 숫자 k> n에 대한 것 입니다.
당신이 원하는 경우 에 비해 2 이상의 작은 힘을 또는 n으로 동일 그럼 그냥 교체 __builtin_clzll(n)에 의해 __builtin_clzll(n-1)위의 조각 내.
GCC 또는 Clang을 사용하는 C ++ 11 (64 비트)
constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
{
return 1ULL << (sizeof(uint64_t) * 8 - __builtin_clzll(n));
}
martinec이CHAR_BIT 제안한대로 사용 향상
#include <cstdint>
constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
{
return 1ULL << (sizeof(uint64_t) * CHAR_BIT - __builtin_clzll(n));
}
GCC 또는 Clang을 사용하는 C ++ 17 (8 ~ 128 비트)
#include <cstdint>
template <typename T>
constexpr T nextPowerOfTwo64 (T n)
{
T clz = 0;
if constexpr (sizeof(T) <= 32)
clz = __builtin_clzl(n); // unsigned long
else if (sizeof(T) <= 64)
clz = __builtin_clzll(n); // unsigned long long
else { // See https://stackoverflow.com/a/40528716
uint64_t hi = n >> 64;
uint64_t lo = (hi == 0) ? n : -1ULL;
clz = _lzcnt_u64(hi) + _lzcnt_u64(lo);
}
return T{1} << (CHAR_BIT * sizeof(T) - clz);
}
기타 컴파일러
GCC 또는 Clang 이외의 컴파일러를 사용하는 경우 Count Leading Zeroes 비트 함수를 나열하는 Wikipedia 페이지를 방문하십시오 .
- 비주얼 C ++ 2005 => 바꾸기
__builtin_clzl()로_BitScanForward() - 비주얼 C ++ 2008 => 바꾸기
__builtin_clzl()로__lzcnt() - ICC => 바꾸기
__builtin_clzl()로_bit_scan_forward - GHC (하스켈) => 대체
__builtin_clzl()하여countLeadingZeros()
기부 환영
의견에 개선 사항을 제안하십시오. 또한 사용하는 컴파일러 또는 프로그래밍 언어에 대한 대안을 제안하십시오.
유사한 답변 참조
x가 음수가 아니라고 가정합니다.
int pot = Integer.highestOneBit(x);
if (pot != x) {
pot *= 2;
}
GCC, MinGW 또는 Clang을 사용하는 경우 :
template <typename T>
T nextPow2(T in)
{
return (in & (T)(in - 1)) ? (1U << (sizeof(T) * 8 - __builtin_clz(in))) : in;
}
If you use Microsoft Visual C++, use function _BitScanForward() to replace __builtin_clz().
function Pow2Thing(int n)
{
x = 1;
while (n>0)
{
n/=2;
x*=2;
}
return x;
}
Bit-twiddling, you say?
long int pow_2_ceil(long int t) {
if (t == 0) return 1;
if (t != (t & -t)) {
do {
t -= t & -t;
} while (t != (t & -t));
t <<= 1;
}
return t;
}
Each loop strips the least-significant 1-bit directly. N.B. This only works where signed numbers are encoded in two's complement.
What about something like this:
int pot = 1;
for (int i = 0; i < 31; i++, pot <<= 1)
if (pot >= x)
break;
You just need to find the most significant bit and shift it left once. Here's a Python implementation. I think x86 has an instruction to get the MSB, but here I'm implementing it all in straight Python. Once you have the MSB it's easy.
>>> def msb(n):
... result = -1
... index = 0
... while n:
... bit = 1 << index
... if bit & n:
... result = index
... n &= ~bit
... index += 1
... return result
...
>>> def next_pow(n):
... return 1 << (msb(n) + 1)
...
>>> next_pow(1)
2
>>> next_pow(2)
4
>>> next_pow(3)
4
>>> next_pow(4)
8
>>> next_pow(123)
128
>>> next_pow(222)
256
>>>
Forget this! It uses loop !
unsigned int nextPowerOf2 ( unsigned int u)
{
unsigned int v = 0x80000000; // supposed 32-bit unsigned int
if (u < v) {
while (v > u) v = v >> 1;
}
return (v << 1); // return 0 if number is too big
}
private static int nextHighestPower(int number){
if((number & number-1)==0){
return number;
}
else{
int count=0;
while(number!=0){
number=number>>1;
count++;
}
return 1<<count;
}
}
// n is the number
int min = (n&-n);
int nextPowerOfTwo = n+min;
#define nextPowerOf2(x, n) (x + (n-1)) & ~(n-1)
or even
#define nextPowerOf2(x, n) x + (x & (n-1))
'IT박스' 카테고리의 다른 글
| React Native에서 기본 글꼴 패밀리를 설정하는 방법은 무엇입니까? (0) | 2020.10.26 |
|---|---|
| 데이터 흐름 프로그래밍 언어 (0) | 2020.10.26 |
| Erlang을 사용하여 "반대"를 결정한 이유는 무엇입니까? (0) | 2020.10.26 |
| 'Z'리터럴로 날짜를 구문 분석하는 simpledateformat (0) | 2020.10.26 |
| 평신도의 용어로 PHP를 사용하는 재귀 함수는 무엇입니까? (0) | 2020.10.26 |