Abscheuliche Zahlen

Eine Zahl gilt als ungerade, wenn sie in ihrer Binärentwicklung eine ungerade Anzahl von Einsen aufweist. Die ersten 10 ungeraden Zahlen sind 1,2,4,7,10,11,13,14,16,19,21. Interessanterweise sind alle Zweierpotenzen ungerade Zahlen, da bei ihnen nur 1 Bit gesetzt ist.

Der folgende Artikel bespricht im Detail zwei Methoden, um festzustellen, ob es sich bei einer Zahl um eine hasserfüllte Zahl handelt.

Problemstellung

Der Zweck dieser Frage besteht darin, zu überprüfen, ob die gegebene Zahl eine abscheuliche Zahl ist, d. h. eine positive Zahl mit einer ungeraden Anzahl gesetzter Bits in ihrer Binärentwicklung.

Ekelhafte Zahlenbeispiele

Input: 34

Output: Non-Odious Number

Anleitung

Die binäre Darstellung von 34 ist 10010.

Stellen Sie die Anzahl der Ziffern = 2 ein.

Da die Anzahl der Einsen eine gerade Zahl ist, ist 34 keine schlechte Zahl.

Input: 1024

Output: Odious Number

Anleitung

Die binäre Darstellung von 1024 ist 10000000000.

Stellen Sie die Anzahl der Ziffern = 1 ein.

Da 1024 eine Potenz von 2 ist, gibt es nur 1 Einstellungsbit. Es ist also eine beängstigende Zahl.

Input: 53

Output: Non-Odious Number

Anleitung

(53)₁₀ = (110101)₂

Anzahl der Ziffern = 4 einstellen.

Es ist also keine abscheuliche Zahl.

Lösung

Um festzustellen, ob eine Zahl hasserfüllt ist, müssen wir wissen, ob die Anzahl der eingestellten Ziffern eine ungerade oder eine gerade Zahl ist. Die Hauptaufgabe besteht hier darin, die Anzahl der bei der Binärentwicklung einer Zahl gesetzten Stellen zu zählen. Die folgende Technik kann verwendet werden, um die Anzahl der Ziffern zu zählen und dann zu prüfen, ob das Ergebnis ungerade oder gerade ist.

Die chinesische Übersetzung von „Naiver Ansatz“ lautet: „Naiver Ansatz“.

Verwenden Sie Schleifen- und Rechtsverschiebungsoperatoren, um alle Ziffern der Zahl nacheinander durchzugehen.

• Wenn der Bitwert 1 ist, erhöhen Sie die Anzahl um eins.

• Überprüfen Sie, ob der Endwert von count ungerade oder gerade ist.

• Antworten anzeigen.

• Pseudocode

Funktion no_of_set_bits()

Initialisierungsanzahl = 0

• wenn (n > 0)

• if ((n & 1) > 0)
     Increment count
  Right Shift n
  

Return count

• Funktion is_odious()

Wenn (Anzahl eine ungerade Zahl ist)

• true zurückgeben

Andere

• Rückgabefehler

Funktion main()

N initialisieren

• Funktionsaufruf no_of_set_bits()

• Funktion is_odious() aufrufen

• Ausdruck

• Beispiel: C++-Programm

Dieses Programm prüft, ob eine Nummer anstößig ist oder nicht. Es überprüft das Bit ganz rechts in jeder Iteration der Schleife, indem es den Wert am Ende jeder Iteration in der Funktion no_of_set_bits() um n nach rechts verschiebt.

#include<iostream>
using namespace std;
// this function counts the number of set bits by analyzing the rightmost bit using a while loop till n > 0.
// it performs logical & operation between 1 and n to determine if the rightmost bit is set or not.
// if it is set, count is incremented by 1
// right shift the value of n to make the bit left of the rightmost bit, the new rightmost bit.
int no_of_set_bits(int n){
   int count = 0;
   while (n > 0){
   
      // if the rightmost bit is 1: increment count
      if ((n & 1) > 0){
         count++;
      }
      
      // right shift the value of n to examine the next bit
      n = n >> 1;
   }
   return count;
}
// this function determines if count of set bits is odd or even
// odd -> odious
bool is_odious(int count){

   // if count is odd return true
   if (count % 2 != 0){
      return true;
   }
   return false;
}

// main function
int main(){
   int n = 27;
   int countBits = no_of_set_bits(n);
   if (is_odious(countBits)){
      cout << n << " is Odious Number";
   }
   else {
      cout << n << " is Non-Odious Number";
   }
   return 0;
}

Ausgabe

27 is Non-Odious Number

Analyse von Zeit und Raum

Zeitkomplexität: O(log(n))

Da die binäre Erweiterung von n log2n Bits erfordert, prüfen wir alle Bits, um zu überprüfen, welche gesetzt sind.

Raumkomplexität: O(1), da kein zusätzlicher Raum verwendet wird.

Die algorithmische Methode von Brian Kernighan Dieser Algorithmus kann verwendet werden, um eine bestimmte Anzahl von Ziffern in einer Zahl effizienter zu berechnen. Mit der Funktion is_odious() kann dann ermittelt werden, ob die Nummer anstößig ist.

Das Grundprinzip dieser Methode besteht darin, das am weitesten rechts gesetzte Bit der Zahl wiederholt zu löschen und dabei zu verfolgen, wie viele Iterationen erforderlich sind, um Null zu erreichen. Die erforderlichen Schritte sind -

Anfangszählung auf 0

• Wenn die Zahl größer als Null ist, führen Sie ein bitweises & zwischen der Zahl und ihrem Zweierkomplement durch, um das am weitesten rechts gesetzte Bit zu deaktivieren.

• Die Anzahl wird bei jeder Schleifeniteration erhöht.

• Überprüfen Sie, ob die Endzählung ungerade ist.

• Ergebnisse anzeigen.

• Beispiel

Die Zahl sei 10. Die binäre Entwicklung von 10 ist 1010. Es ist zu erkennen, dass es über 2 Setzbits verfügt.

Schleifeniteration 1 -

n = 10
n & (n-1) =  10 & 9
1010   (n)
1001   (n - 1)
1000   (n = 8)

Schleifeniteration 2 -

n = 8
n & (n-1) = 8 & 7
1000    (n)
0111	(n-1)
0       (n = 0) 

Anzahl der Iterationen = Anzahl der Einstellungen = 2. Pseudocode

Funktion no_of_set_bits()

Initialisierungsanzahl = 0

• wenn (n > 0)

• n = n & (n-1)

Anzahl erhöhen
Return count

• Funktion is_odious()

Gleiche wie die vorherige Methode

Funktion main()

Gleiche wie die vorherige Methode

Beispiel: C++-Programm

Dieses Programm berechnet die Anzahl der gesetzten Bits, indem es die Anzahl der Iterationen zählt, die erforderlich sind, um alle gesetzten Bits zu löschen. Um Bits zu löschen, führen wir eine bitweise UND-Operation für n und n-1 durch. Dies liegt daran, dass die binäre Darstellung von n-1 das am weitesten rechts gesetzte Bit von n und alle darauf folgenden Bits umdreht.

#include<iostream>
using namespace std;
// this function counts the number of set bits by unsetting the rightmost set bit using a while loop till n > 0.
// it performs logical & operation between n and n - 1 to unset the rightmost set bit.
// count is incremented in every iteration
int no_of_set_bits(int n){
   int count = 0;
   while (n > 0){
      // update the value of n to unset the current rightmost set bit
      n = n & (n - 1);
      count++;
   }
   return count;
}

// this function determines if count of set bits is odd or even
// odd -> odious
bool is_odious(int count){

   // if count is odd return true
   if (count % 2 != 0){
      return true;
   }
   return false;
}

// main function
int main(){
   int n = 27;
   int countBits = no_of_set_bits(n); // function call
   if (is_odious(countBits)){
      cout << n << " is Odious Number";
   }
   else {
      cout << n << " is Non-Odious Number";
   }
   return 0;
}

Ausgabe

27 is Non-Odious Number

Raum-Zeit-Analyse

Zeitkomplexität

– O(log(x)), wobei x die Anzahl der in der Zahl festgelegten Ziffern ist. Wenn nur 1 Bit gesetzt ist, wird die Schleife einmal durchlaufen.

Raumkomplexität – O(1), da kein zusätzlicher Raum verwendet wird.

Vergleichen Sie die oben genannten Methoden

Während die erste Methode ziemlich einfach zu verstehen ist, erfordert sie Log(n)-Iterationen, um das Endergebnis zu erzielen. Die zweite Methode hingegen verwendet die Log(x)-Iteration, wobei x die Anzahl der Ziffern ist, die in der binären Erweiterung der Zahl festgelegt werden. Daher verbessert es die Leistung.

Fazit

In diesem Artikel werden zwei Möglichkeiten besprochen, um zu überprüfen, ob eine Zahl ekelhaft ist. Außerdem erhalten wir das Konzept der Methode, Beispiele, verwendete Algorithmen, C++-Programmlösungen und eine Komplexitätsanalyse jeder Methode. Außerdem wurden die beiden Methoden verglichen, um festzustellen, welche effektiver war.

Das obige ist der detaillierte Inhalt vonAbscheuliche Zahlen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!