AND von allen natürlichen Zahlen zwischen A und B beide inklusive

Question

Wir sind verpflichtet, die bit weise UND unter allen natürlichen Zahlen zwischen A und B, beide inklusive zu berechnen. Ich stieß auf eine Website auf dieses Problem und hier ist der Ansatz sie benutzten, aber ich konnte die Methode nicht verstehen. Kann jemand das mit einem Beispiel deutlicher erklären?

Um dieses Problem zu lösen, müssen wir uns nur auf die Vorkommen jeder Potenz 2 konzentrieren, die sich als zyklisch herausstellt. Jetzt für jedes 2^i (die Länge des Zyklus wird 2^(i + 1) mit 2^i Nullen, gefolgt von der gleichen Anzahl von Einsen) müssen wir nur berechnen, wenn 1 in dem gegebenen Intervall konstant bleibt, was getan wird durch einfache Arithmetik. Wenn dies der Fall ist, wird diese Zweierpotenz in der Antwort vorhanden sein, andernfalls nicht.

Answer 1

Lassen Sie uns count (unsigned) mit 3 Bits zunächst einige Zahlen zu visualisieren:

000 = 0 
001 = 1 
010 = 2 
011 = 3 
100 = 4 
101 = 5 
110 = 6 
111 = 7 

Wenn man sich die Spalten suchen, können Sie das niedrigste Bit mit einem Zyklus von 1 abwechseln, die nächste sehen, dass mit ein Zyklus von 2, dann 4, und das niedrigste n-te Bit wechselt mit einem Zyklus von 2^(n-1).

Sobald ein Bit einmal 0 war, ist es immer 0 (weil 0 und was auch immer 0 ist).

Sie könnten auch das sagen n te Bit ist nur 1 wenn die n te Bit A und B1 und d < 2^(n-1) ist. Mit anderen Worten, ein Bit ist nur 1, wenn es zu Beginn und am Ende 1 ist und keine Zeit hatte, dazwischen auf 0 zu wechseln, weil sein Zyklus zu groß ist.