Anzahl der Einsen in binärer Darstellung zählen

Effiziente Methode zum Zählen der Anzahl von Einsen in der binären Darstellung einer Zahl in O (1), wenn Sie über genügend Speicher zum Spielen verfügen. Dies ist eine Interviewfrage, die ich in einem Online-Forum gefunden habe, die aber keine Antwort hatte. Kann jemand etwas vorschlagen, ich kann mir keinen Weg vorstellen, es in O (1) Zeit zu tun?

Das ist das Hamming-Gewichtsproblem , auch bekannt als Bevölkerungszahl. Der Link erwähnt effiziente Implementierungen. Zitat:

Mit unbegrenztem Speicher könnten wir einfach eine große Nachschlagetabelle des Hamming-Gewichts jeder 64-Bit-Ganzzahl erstellen

Ich habe eine Lösung, die die Bits in der O(Number of 1's)Zeit zählt:

bitcount(n):
    count = 0
    while n > 0:
        count = count + 1
        n = n & (n-1)
    return count

Im schlimmsten Fall (wenn die Zahl 2 ^ n - 1 ist, sind alle 1 binär) wird jedes Bit überprüft.

Bearbeiten: Habe gerade einen sehr schönen Algorithmus mit konstanter Zeit und konstantem Speicher für Bitcount gefunden. Hier ist es, geschrieben in C:

int BitCount(unsigned int u)
{
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}

Den Beweis für die Richtigkeit finden Sie hier .

Bitte beachten Sie, dass: n & (n-1) immer die niedrigstwertige 1 eliminiert.

Daher können wir den Code zur Berechnung der Anzahl der Einsen wie folgt schreiben:

count=0;
while(n!=0){
  n = n&(n-1);
  count++;
}
cout<<"Number of 1's in n is: "<<count;

Die Komplexität des Programms wäre: Anzahl der Einsen in n (was konstant <32 ist).

Ich habe die folgende Lösung von einer anderen Website gesehen:

int count_one(int x){
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
    return x;
}

public static void main(String[] args) {

    int a = 3;
    int orig = a;
    int count = 0;
    while(a>0)
    {
        a = a >> 1 << 1;
        if(orig-a==1)
            count++;
        orig = a >> 1;
        a = orig;
    }

    System.out.println("Number of 1s are: "+count);
}

   countBits(x){
     y=0;
     while(x){   
       y += x &  1 ;
       x  = x >> 1 ;
     }
   }

das ist es?

Das wird die kürzeste Antwort in meinem SO-Leben sein: Nachschlagetabelle.

Anscheinend muss ich ein wenig erklären: "Wenn Sie genug Speicher zum Spielen haben" bedeutet, dass wir über den gesamten Speicher verfügen, den wir benötigen (ungeachtet der technischen Möglichkeit). Jetzt müssen Sie die Nachschlagetabelle nicht länger als ein oder zwei Bytes speichern. Während es technisch gesehen eher Ω (log (n)) als O (1) ist, ist das Lesen einer benötigten Zahl Ω (log (n)). Wenn dies also ein Problem ist, ist die Antwort unmöglich - was ist noch kürzer.

Welche von zwei Antworten sie bei einem Interview von Ihnen erwarten, weiß niemand.

Es gibt noch einen weiteren Trick: Während Ingenieure eine Zahl nehmen und über Ω (log (n)) sprechen können, wobei n die Zahl ist, werden Informatiker sagen, dass wir die Laufzeit tatsächlich als Funktion der Länge einer Eingabe messen müssen Das, was Ingenieure Ω (log (n)) nennen, ist tatsächlich Ω (k), wobei k die Anzahl der Bytes ist. Wie ich bereits sagte, ist das Lesen einer Zahl Ω (k). Wir können es also auf keinen Fall besser machen.

Unten wird auch funktionieren.

nofone(int x) {
  a=0;
  while(x!=0) {
    x>>=1;
    if(x & 1)
      a++;
  }
  return a;
} 

Das Folgende ist eine C-Lösung mit Bitoperatoren:

int numberOfOneBitsInInteger(int input) {
  int numOneBits = 0;

  int currNum = input;
  while (currNum != 0) {
    if ((currNum & 1) == 1) {
      numOneBits++;
    }
    currNum = currNum >> 1;
  }
  return numOneBits;
}

Das Folgende ist eine Java-Lösung mit Potenzen von 2:

public static int numOnesInBinary(int n) {

  if (n < 0) return -1;

  int j = 0;
  while ( n > Math.pow(2, j)) j++;

  int result = 0;
  for (int i=j; i >=0; i--){
    if (n >= Math.pow(2, i)) {
        n = (int) (n - Math.pow(2,i));
        result++;    
    }
  }

  return result;
}

Im Folgenden finden Sie zwei einfache Beispiele (in C ++) unter vielen, anhand derer Sie dies tun können.

1. Wir können einfach gesetzte Bits (Einsen) mit __builtin_popcount () zählen.

   int numOfOnes(int x) { return __builtin_popcount(x); }

2. Durchlaufen Sie alle Bits in einer Ganzzahl, prüfen Sie, ob ein Bit gesetzt ist, und erhöhen Sie dann die Zählvariable.

   int hammingDistance(int x) { int count = 0 for(int i = 0; i < 32; i++) if(x & (1 << i)) count++; return count; }

Hoffe das hilft!

Die Funktion nimmt ein intund gibt die Anzahl der Einen in binärer Darstellung zurück

public static int findOnes(int number)
{

   if(number < 2)
    {
        if(number == 1)
        {
            count ++;
        }
        else
        {
            return 0;
        }
    }

    value = number % 2;

    if(number != 1 && value == 1)
        count ++;

    number /= 2;

    findOnes(number);

    return count;
}

Der beste Weg in Javascript ist dies

function getBinaryValue(num){
 return num.toString(2);
}

function checkOnces(binaryValue){
    return binaryValue.toString().replace(/0/g, "").length;
}

Dabei ist binaryValue der binäre String, z. B.: 1100

Es gibt nur einen Weg, wie ich mir vorstellen kann, diese Aufgabe in O (1) zu erfüllen ... nämlich ein physisches Gerät zu "betrügen" und zu verwenden (bei linearer oder sogar paralleler Programmierung denke ich, dass die Grenze O ist (log (k)). wobei k die Anzahl der Bytes der Anzahl darstellt).

Sie können sich jedoch sehr leicht ein physisches Gerät vorstellen, das jedes Bit und eine Ausgangsleitung mit einer Spannung von 0/1 verbindet. Dann können Sie einfach die Gesamtspannung auf einer Summationsleitung in O (1) elektronisch ablesen. Es wäre ziemlich einfach, diese Grundidee mit einigen grundlegenden Schaltungselementen eleganter zu gestalten, um die Ausgabe in einer beliebigen Form zu erzeugen (z. B. eine binär codierte Ausgabe), aber die wesentliche Idee ist dieselbe und die elektronische Schaltung würde die richtige Ausgabe erzeugen Zustand in fester Zeit.

Ich stelle mir vor, dass es auch Möglichkeiten für Quantencomputer gibt, aber wenn wir das dürfen, würde ich denken, dass eine einfache elektronische Schaltung die einfachere Lösung ist.

Ich habe dies tatsächlich mit ein wenig Fingerspitzengefühl getan: Eine einzelne Nachschlagetabelle mit 16 Einträgen wird ausreichen, und alles, was Sie tun müssen, ist, die binäre Wiederholung in Halbbytes (4-Bit-Tupel) zu zerlegen. Die Komplexität ist in der Tat O (1) und ich habe eine C ++ - Vorlage geschrieben, die auf die Größe der gewünschten Ganzzahl (in # Bits) spezialisiert war. Dies macht sie zu einem konstanten Ausdruck anstatt zu einem unbestimmten.

fwiw können Sie die Tatsache nutzen, dass (i & -i) Ihnen das LS-Ein-Bit zurückgibt und einfach eine Schleife abgibt, wobei jedes Mal das lsbit entfernt wird, bis die Ganzzahl Null ist - aber das ist ein alter Paritätstrick.

Ich kam hierher mit dem großen Glauben, dass ich eine schöne Lösung für dieses Problem kenne. Code in C:

    short numberOfOnes(unsigned int d) {
        short count = 0;

        for (; (d != 0); d &= (d - 1))
            ++count;

        return count;
    }

Aber nachdem ich ein wenig zu diesem Thema recherchiert habe (andere Antworten lesen :)), habe ich 5 effizientere Algorithmen gefunden. Liebe so!

Es gibt sogar einen CPU-Befehl, der speziell für diese Aufgabe entwickelt wurde : popcnt. (in dieser Antwort erwähnt )

Beschreibung und Benchmarking vieler Algorithmen finden Sie hier .

Die folgende Methode kann auch die Anzahl der Einsen in negativen Zahlen zählen.

private static int countBits(int number)    {
    int result = 0;
    while(number != 0)  {
        result += number & 1;
        number = number >>> 1;
    }
    return result;
}

Eine Zahl wie -1 wird jedoch binär als 111111111111111111111111111111 dargestellt und erfordert daher viele Verschiebungen. Wenn Sie nicht so viele Schichten für kleine negative Zahlen machen möchten, könnte ein anderer Weg wie folgt sein:

private static int countBits(int number)    {
    boolean negFlag = false;
    if(number < 0)  { 
        negFlag = true;
        number = ~number;
    }

    int result = 0;
    while(number != 0)  {
        result += number & 1;
        number = number >> 1;
    }
    return negFlag? (32-result): result;
}

In Python oder einem anderen Konvertierungs-Bin-String teilen Sie ihn dann mit '0', um Nullen zu entfernen. Kombinieren Sie ihn dann und ermitteln Sie die Länge.

len(''.join(str(bin(122011)).split('0')))-1

Durch Verwendung von String-Operationen von JS kann man wie folgt vorgehen:

0b1111011.toString(2).split(/0|(?=.)/).length // returns 6

oder

0b1111011.toString(2).replace("0","").length  // returns 6

Ich musste dies in Rubin spielen und endete mit

l=->x{x.to_s(2).count ?1}

Verwendung :

l[2**32-1] # returns 32

Offensichtlich nicht effizient, macht aber den Trick :)

Ruby-Implementierung

def find_consecutive_1(n)
  num = n.to_s(2)
  arr = num.split("")
  counter = 0
  max = 0
  arr.each do |x|
      if x.to_i==1
          counter +=1
      else
          max = counter if counter > max
          counter = 0 
      end
      max = counter if counter > max  
  end
  max
end

puts find_consecutive_1(439)

Zwei Wege::

/* Method-1 */
int count1s(long num)
{
    int tempCount = 0;

    while(num)
    {
        tempCount += (num & 1); //inc, based on right most bit checked
        num = num >> 1;         //right shift bit by 1
    }

    return tempCount;
}

/* Method-2 */
int count1s_(int num)
{
    int tempCount = 0;

    std::string strNum = std::bitset< 16 >( num ).to_string(); // string conversion
    cout << "strNum=" << strNum << endl;
    for(int i=0; i<strNum.size(); i++)
    {
        if('1' == strNum[i])
        {
            tempCount++;
        }
    }

    return tempCount;
}

/* Method-3 (algorithmically - boost string split could be used) */
1) split the binary string over '1'.
2) count = vector (containing splits) size - 1

Verwendung::

    int count = 0;

    count = count1s(0b00110011);
    cout << "count(0b00110011) = " << count << endl; //4

    count = count1s(0b01110110);
    cout << "count(0b01110110) = " << count << endl;  //5

    count = count1s(0b00000000);
    cout << "count(0b00000000) = " << count << endl;  //0

    count = count1s(0b11111111);
    cout << "count(0b11111111) = " << count << endl;  //8

    count = count1s_(0b1100);
    cout << "count(0b1100) = " << count << endl;  //2

    count = count1s_(0b11111111);
    cout << "count(0b11111111) = " << count << endl;  //8

    count = count1s_(0b0);
    cout << "count(0b0) = " << count << endl;  //0

    count = count1s_(0b1);
    cout << "count(0b1) = " << count << endl;  //1