Angenommen, ich muss alle Bits vor einem bestimmten Bit-Index setzen. Hier sind einige Beispiele mit 4 Bits:Setze Bits vor dem Index ohne Verschiebung oder LUT
index(0) = (0x0, 0000)
index(1) = (0x1, 1000)
index(2) = (0x3, 1100)
index(3) = (0x7, 1110)
Wie kann ich dies tun, ohne Verschiebungen oder eine LUT verwendet wird, sondern mit minimalen bitweise Operationen oder arithmetische oder etwas ähnlich leistungsfähig?
Die Einschränkungen sind sehr seltsam, weil Sie eine effiziente Lösung und Schnitt von nur zwei Mittel wollen, um es richtig zu machen.
Sie wollen also im Grunde x=(2^bit)-1 zu berechnen, die mit Bit-Verschiebung ist recht einfach:
x=(1<<bit)-1; // O(1)
Mit LUT ... auch so, wie dies zu attackieren, ohne dass die beiden:
x=pow(2,bit)-1; //O(?) can be O(1),O(log(n)),O(n)
Nun, das ist weit von effizient und pow verwendet auch Bit-Shift und einige Implementierung auch LUT. Die einzigen Lösungen links sind:
Annäherung
kann Polynom, PCA verwenden, oder jede andere Methode ... aber Sie müssen den Zielbereich prüfen ... Dies ist auch nicht sehr optimal und robust. Dies kann O(1),O(log(n)),O(n) sein, aber normalerweise mit sehr langsamer konstanter Zeit.
emulieren Bit-shif links
Sie können mit Schleife und zusätzlich zu tun:
int x; for (x=1;bit;bit--) x+=x; x--;
Aber in O(n) läuft. Wie auch immer, das ist immer noch schneller als pow, es sei denn, Sie haben pow2 implementiert auf HW.
[Anmerkungen]
in der Komplexität Formeln n=bit und der gesamte Code ist in C++ mit Ausnahme der ersten Formel in der ^ Leistungsmittel.
Bits zählen beginnt von rechts nach links in der Regel –
Wie qualifiziert sich eine Schicht nicht als minimale bitweise Operation? –
@JerryCoffin - es ist auf einigen Systemen als mehrere Operationen (GPUs zum Beispiel) implementiert – user1043761