Wie kann ich feststellen, ob eine Zahl ein Vielfaches von vier ist und nur den logischen Operator AND verwendet?

Question

Ich bin mit Assembler Programmierung und ich bin gespannt, wie ich sagen könnte, wenn eine Zahl ein Vielfaches von 4 mit dem logischen Operator UND ist?

Ich weiß, wie es mit "Div" oder "Rest" Anweisungen zu tun, aber ich versuche, dies mit Bit-Manipulation von Nummer/Wort zu tun.

Kann mir jemand in die richtige Richtung zeigen? Ich benutze MIPs, aber eine sprachunabhängige Antwort ist in Ordnung.

Answer 1

Nun, um festzustellen, ob eine Nummer ein Vielfaches von einem anderen ist, müssen Sie einfach x MOD y tun. Wenn das Ergebnis 0 ist, dann ist es ein gerades Vielfaches.

Es ist auch wahr, dass für jeden y, die eine Leistung von 2 ist, (x MOD y)-(x AND (y - 1)) entspricht.

Deshalb:

IF (x AND 3) == 0 THEN 
    /* multiple of 4 */ 

EDIT:

ok, möchten Sie warum(x MOD y) == (x AND (y - 1)) wissen, wann y eine Potenz von 2 ist, ich mein Bestes tun, um zu erklären.

Wenn eine Zahl eine Potenz von 2 ist, wird ein einzelnes Bit gesetzt (binary ist Base 2). Dies bedeutet, dass alle unteren Bits nicht gesetzt sind. So zum Beispiel: 16 == 10000b, 8 == 1000b usw.

Wenn Sie 1 von einem dieser Werte subtrahieren. Sie haben am Ende das Bit gesetzt, das nicht gesetzt wurde und alle Bits darunter gesetzt sind.

15 = 01111b, 7 = 0111b, usw. Also im Grunde ist es erstellt eine Maske, die verwendet werden kann, um zu testen, ob die unteren Bits gesetzt wurden. Ich hoffe, das war klar.

EDIT: Bastien Léonard Kommentar deckt es gut zu:

wenn Sie teilen (unsigned) von 4, zwei Bits nach rechts verschieben . Somit ist der Rest diese zwei Bits, die verloren gehen, wenn Sie teilen. 4 - 1 = 11b, das heißt, eine Maske, die die beiden am weitesten rechts liegenden Bits ergibt, wenn Sie es mit einem Wert UND.

EDIT: sehen Aktualisierung möglicherweise klarer Erklärungen: http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_check_if_a_positive_number_is_a_power_of_two.

Es umfasst Potenzen von 2 und mit AND als schnelle Modulo-Operation erkennen, ob es sich um eine Potenz von 2

Answer 2

(x & 3) == 0

w.r.t. Assemblersprache, verwenden Sie TST, falls verfügbar, andernfalls AND und überprüfen Sie das Null-Flag.

Answer 3

Eine Zahl ist ein Vielfaches von 4, wenn die unteren 2 Bits 0 sind. Sie können die Zahl also einfach zweimal nach rechts verschieben und die verschobenen Bits auf 0 setzen.

Answer 4

In x86 Montage:

test eax, 3 
    jnz not_multiple_of_4 

    ; action to be taken if EAX is a multiple of 4 

not_multiple_of_4: 
    ; ...