Bedeutung von bitweisem und (&) einer positiven und negativen Zahl?

Question

Kann mir jemand helfen was n&-n bedeutet ?? Und was ist die Bedeutung davon.

Answer 1

Ich glaube, es ist ein Trick, um herauszufinden, ob n eine Potenz von 2 ist. (N == (n & -n)) IFF n ist eine Potenz von 2 (1,2,4,8).

Answer 2

Auf so ziemlich jedem System, das die meisten Menschen wirklich interessieren, wird es Ihnen die höchste Macht von 2 geben, dass n gleichmäßig durch teilbar ist.

Answer 3

Es ist nur ein bitweises und der Nummer. Negative Zahlen werden als two's complement dargestellt.

So zum Beispiel, bitweise und von 7 & (-7) ist x00000111 & x11111001 = x00000001 = 1

Answer 4

Es ist ein alter Trick, der in einer Zahl mit einem einzigen Bit gibt, das untere Bit, das gesetzt wurde in n. Zumindest in der Zweierkomplement-Arithmetik, die heutzutage fast universell ist.

Der Grund, warum es funktioniert: das Negativ einer Zahl wird durch Invertieren der Zahl erzeugt, dann 1 (das ist die Definition von Zweierkomplement). Wenn Sie 1 hinzufügen, wird jedes Bit, das an der untersten Stelle beginnt, in das nächsthöhere Bit überlaufen; Dies stoppt, sobald Sie ein Null-Bit erreichen. Diese übergelaufenen Bits sind alle null, und die Bits über dem letzten betroffenen sind die Inverse voneinander, so dass das einzige übriggebliebene Bit derjenige ist, der die Kaskade gestoppt hat - diejenige, die als 1 gestartet und auf 0 invertiert wurde.

PS Wenn Sie sich Sorgen machen über über eine-Arithmetik läuft hier eine Version, die mit beiden Werken:

n & (~n + 1) 

Answer 5

Wie @aestrivex erwähnt hat, ist es eine Möglichkeit, 1.Even des Schreibens ich dieses begegnet

for (int y = x; y > 0; y -= y & -y) 

und es bedeutet nur, y = y-1, da
(-7) ist x00000111 & x11111001 = x00000001 = 1

Answer 6

I die 0.123.457 ein selbsterklärendes Beispiel hinzufügen würde's wunderbare Ausstellung.

010010000 | +144 ~ 
----------|------- 
101101111 | -145 + 
     1 | 
----------|------- 
101110000 | -144 

101110000 | -144 & 
010010000 | +144 
----------|------- 
000010000 | 16` 

Answer 7

Weil x & -x = {0, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32} für x von 0 bis 32. Es ist für einige Anwendungen zu sprunghaft in die für Sequenzen verwendet. Die Anwendungen können gespeicherte Datensätze speichern.

for(;x < N;x += x&-x) { 
    // do something here 
    ++tr[x]; 
} 

Die Schleife überquert sehr schnell, weil sie nach der nächsten Potenz von zwei sucht, um zu springen.