wake-up-neo.com

Wie finde ich bei einer gegebenen Ganzzahl die nächstgrößere Zweierpotenz mit Bit-Twiddling?

Wenn ich eine Ganzzahl n habe, wie kann ich die nächste Zahl k > n Finden, so dass k = 2^i Mit einem i -Element von N durch bitweise Verschiebung oder Logik.

Beispiel: Wenn ich n = 123 Habe, wie finde ich dann k = 128, Eine Potenz von zwei, und nicht 124, Die nur durch zwei teilbar ist? Das sollte einfach sein, aber es entzieht sich mir.

72
AndreasT

Für 32-Bit-Ganzzahlen ist dies eine einfache und unkomplizierte Route:

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.

Hier ist ein konkreteres Beispiel. Nehmen wir die Zahl 221, die binär 11011101 ist:

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

Es gibt ein Bit an der neunten Position, das 2 ^ 8 darstellt, oder 256, was in der Tat die zweitgrößte Potenz von 2 ist. Jede der Verschiebungen überlappt alle vorhandenen 1-Bits in der Nummer mit einigen der zuvor unberührten Nullen und erzeugt schließlich eine Anzahl von 1-Bits, die der Anzahl von Bits in der ursprünglichen Nummer entspricht. Wenn Sie diesen Wert um eins erhöhen, erhalten Sie eine neue Potenz von 2.

Ein anderes Beispiel; Wir werden 131 verwenden, das heißt 10000011 in binärer Form:

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

Und in der Tat ist 256 die zweithöchste Potenz von 131.

Wenn die Anzahl der zur Darstellung der Ganzzahl verwendeten Bits selbst eine Zweierpotenz ist, können Sie diese Technik effizient und unbegrenzt erweitern (fügen Sie beispielsweise ein n >> 32 Zeile für 64-Bit-Ganzzahlen).

94
John Feminella

Es gibt tatsächlich eine Assembly-Lösung dafür (seit dem Befehlssatz 80386).

Mit der Anweisung BSR (Bit Scan Reverse) können Sie nach dem höchstwertigen Bit in Ihrer Ganzzahl suchen.

bsr durchsucht die Bits beginnend mit dem höchstwertigen Bit im Doppelwortoperanden oder im zweiten Wort. Wenn alle Bits Null sind, wird ZF gelöscht. Andernfalls wird ZF gesetzt und der Bitindex des zuerst gefundenen gesetzten Bits beim Abtasten in umgekehrter Richtung in das Zielregister geladen

(Auszug aus: http://dlc.Sun.com/pdf/802-1948/802-1948.pdf )

Und dann das Ergebnis mit 1.

so:

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

In neueren CPUs können Sie die viel schnellere Anweisung lzcnt verwenden (auch bekannt als rep bsr). lzcnt erledigt seine Arbeit in einem einzigen Zyklus.

29
Davy Landman

Ein mathematischer Weg ohne Schleifen:

public static int ByLogs(int n)
{
    double y = Math.Floor(Math.Log(n, 2));

    return (int)Math.Pow(2, y + 1);
}
21
DanDan

Hier ist eine logische Antwort:

function getK(int n)
{
  int k = 1;
  while (k < n)
    k *= 2;
  return k;
}
12
JustLoren

Hier ist John Feminellas Antwort, die als Schleife implementiert wurde, damit sie mit langen Python-Ganzzahlen umgehen kann:

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

Es kehrt auch schneller zurück, wenn n bereits eine Potenz von 2 ist.

Für Python> 2.7 ist dies für die meisten N einfacher und schneller:

def next_power_of_2(n):
    """
    Return next power of 2 greater than or equal to n
    """
    return 2**(n-1).bit_length()

enter image description here

8
endolith

Hier ist eine wilde, die keine Schleifen hat, aber einen Zwischenschwimmer verwendet.

//  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;

Dieser und viele andere Bit-Twiddling-Hacks, einschließlich des von John Feminella eingereichten On, sind hier zu finden .

3
I. J. Kennedy

Größer als/Größer als oder gleich

Die folgenden Ausschnitte sind für die nächste Zahl k> n, so dass k = 2 ^ i
(n = 123 => k = 128, n = 128 => k = 256) nach OP.

Wenn Sie die kleinste Potenz von 2 größer als OR gleich n wollen, dann ersetzen Sie einfach __builtin_clzll(n) by __builtin_clzll(n-1) in den obigen Ausschnitten.

C++ 11 mit GCC oder Clang (64 Bit)

constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
{
    return 1ULL << (sizeof(uint64_t) * 8 - __builtin_clzll(n));
}

Erweiterung mit CHAR_BIT wie von martinec vorgeschlagen

#include <cstdint>

constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
{
    return 1ULL << (sizeof(uint64_t) * CHAR_BIT - __builtin_clzll(n));
}

C++ 17 mit GCC oder Clang (von 8 bis 128 Bit)

#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);
}

Andere Compiler

Wenn Sie einen anderen Compiler als GCC oder Clang verwenden, besuchen Sie bitte die Wikipedia-Seite, auf der die Funktionen Count Leading Zeroes bitwise aufgeführt sind:

  • Visual C++ 2005 => Ersetzen Sie __builtin_clzl() durch _BitScanForward()
  • Visual C++ 2008 => Ersetzen Sie __builtin_clzl() durch __lzcnt()
  • icc => Ersetze __builtin_clzl() durch _bit_scan_forward
  • GHC (Haskell) => Ersetze __builtin_clzl() durch countLeadingZeros()

Beitrag willkommen

Bitte schlagen Sie Verbesserungen in den Kommentaren vor. Schlagen Sie auch eine Alternative für den von Ihnen verwendeten Compiler oder Ihre Programmiersprache vor ...

Siehe auch ähnliche Antworten

3
olibre

nehme an, x ist nicht negativ.

int pot = Integer.highestOneBit(x);
if (pot != x) {
    pot *= 2;
}
2
Alex Cohn

Wenn Sie GCC, MinGW oder Clang verwenden:

template <typename T>
T nextPow2(T in)
{
  return (in & (T)(in - 1)) ? (1U << (sizeof(T) * 8 - __builtin_clz(in))) : in;
}

Wenn Sie Microsoft Visual C++ verwenden, ersetzen Sie _BitScanForward() durch __builtin_clz().

2
nulleight
function Pow2Thing(int n)
{
    x = 1;
    while (n>0)
    {
        n/=2;
        x*=2;
    }
    return x;
}
1
Rik Heywood

Bit-Twiddling, sagst du?

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;
}

Jede Schleife entfernt das niedrigstwertige 1-Bit direkt. N.B. Dies funktioniert nur, wenn vorzeichenbehaftete Zahlen im Zweierkomplement codiert sind.

1
Derek Illchuk
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;
    }
}
0
lavish

Was ist mit so etwas:

int pot = 1;
for (int i = 0; i < 31; i++, pot <<= 1)
    if (pot >= x)
        break;
0
Eric

Vergiss das! Es verwendet Schleife!

     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
     }
0
nunkown

Sie müssen nur das höchstwertige Bit finden und es einmal nach links verschieben. Hier ist eine Python Implementierung. Ich denke, x86 hat eine Anweisung, um das MSB zu bekommen, aber hier implementiere ich alles in direktem Python. Sobald Sie das MSB haben, ist es einfach.

>>> 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
>>>
0
FogleBird