Policz liczbę 1 w reprezentacji binarnej

Mam rozwiązanie, które zlicza bity w O(Number of 1's) czasie:

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

W najgorszym przypadku (gdy liczba jest 2^n - 1, Wszystkie 1 w binarnym) sprawdza każdy bit.

Edytuj: Właśnie znalazłem bardzo ładny algorytm stałej pamięci dla bitcount. Oto jest, napisane w C:

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

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

Możesz znaleźć dowód jego poprawności tutaj.

Zwróć uwagę na fakt, że: n&(n-1) zawsze eliminuje najmniej znaczące 1.

Stąd możemy napisać kod do obliczenia liczby 1 w następujący sposób:

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

Złożoność programu byłaby: liczba 1 W n (która jest stale

Widziałem następujące rozwiązanie z innej strony:

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 ;
     }
   }

To będzie Najkrótsza odpowiedź w moim życiu: Tabela wyszukiwania.

Najwyraźniej muszę trochę wyjaśnić: "jeśli masz wystarczająco dużo pamięci do zabawy" oznacza, że mamy całą pamięć, której potrzebujemy (możliwość techniczna nevermind). Teraz nie musisz przechowywać tabeli wyszukiwania przez więcej niż jeden lub dwa bajty. Chociaż technicznie będzie to Ω(log (n)) zamiast O (1), wystarczy odczytać liczbę, której potrzebujesz, to Ω(log (N)), więc jeśli to problem, to odpowiedź brzmi:, impossible-który jest jeszcze krótszy.

Której z dwóch odpowiedzi oczekują od Ciebie na rozmowie kwalifikacyjnej, nikt nie wie.

Jest jeszcze jedna sztuczka: podczas gdy inżynierowie mogą wziąć liczbę i mówić o Ω(log(n)), gdzie n jest liczbą, informatycy powiedzą, że w rzeczywistości mamy mierzyć czas pracy jako funkcję długości wejścia, więc to, co inżynierowie nazywają Ω(log(N)), jest w rzeczywistości Ω (k), gdzie k jest liczbą bajtów. Jednak, jak już mówiłem, po prostu odczytanie liczby jest Ω (k), więc nie ma mowy, żebyśmy mogli zrobić coś lepszego.

Poniżej również będzie działać.

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

Poniżej znajduje się rozwiązanie C wykorzystujące operatory bitowe:

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

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

Poniżej znajduje się rozwiązanie Java wykorzystujące uprawnienia 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;
}

Poniżej znajdują się dwa proste przykłady (w C++) spośród wielu, za pomocą których można to zrobić.

1. Możemy po prostu policzyć ustawione bity (1) za pomocą _ _ builtin _ popcount ().

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

2. W pętli przez wszystkie bity w liczbie całkowitej, sprawdź, czy bit jest ustawiony i jeśli jest to zwiększenie zmiennej count.

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

Funkcja przyjmuje int i zwraca liczbę jedynek w reprezentacji binarnej

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;
}

Najlepszym sposobem w javascript jest

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

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

Gdzie binaryValue jest ciągiem binarnym np: 1100

Jest tylko jeden sposób, który mogę wymyślić, aby wykonać to zadanie w O(1)... to jest "oszukiwać" i używać urządzenia fizycznego(z programowania liniowego lub nawet równoległego myślę, że limit jest O(log (k)), gdzie k oznacza liczbę bajtów liczby).

Można jednak bardzo łatwo wyobrazić sobie fizyczne urządzenie, które łączy każdy bit an z linią wyjściową napięciem 0/1. Następnie można było elektronicznie odczytać całkowite napięcie na linii "sumowania" w O(1). Byłoby to dość łatwe do uczynić ten podstawowy pomysł bardziej elegancki z niektórych podstawowych elementów obwodu do produkcji wyjście w dowolnej formie, jaką chcesz( np binarne kodowane wyjście), ale zasadnicza idea jest taka sama i obwód elektroniczny będzie produkować poprawny stan wyjściowy w ustalonym czasie.

Wyobrażam sobie, że są też możliwe możliwości obliczeń kwantowych, ale jeśli nam to wolno, to myślę, że prostym układem elektronicznym jest łatwiejsze rozwiązanie.

Zrobiłem to za pomocą odrobiny sprytu: wystarczy pojedyncza tabela wyszukiwania z 16 wpisami, a wszystko, co musisz zrobić, to rozbić binarny rep na nibbles (4-bitowe krotki). Złożoność jest w rzeczywistości O (1) i napisałem szablon C++, który był wyspecjalizowany w rozmiarze liczby całkowitej, którą chciałeś (w # bitach) ... sprawia, że jest to wyrażenie stałe zamiast nieokreślone.

Fwiw możesz wykorzystać fakt, że (i & -i) zwróci ci jednobitowy LS i po prostu pętlę, zdejmując lsbit za każdym razem, dopóki liczba całkowita nie będzie równa zero-ale to stara sztuczka parzystości.

Przybyłem tu z wielkim przekonaniem, że znam piękne rozwiązanie tego problemu. Kod w C:

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

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

        return count;
    }

Ale po trochę badań na ten temat (czytaj inne odpowiedzi:)) znalazłem 5 bardziej wydajnych algorytmów. Love SO!

Istnieje nawet Instrukcja CPU zaprojektowana specjalnie do tego zadania: popcnt. (wymienione w ta odpowiedź )

Opis i benchmarking wielu algorytmów można znaleźć tutaj .

Poniższa metoda może również liczyć liczbę 1s w liczbach ujemnych.

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

Jednak liczba jako -1 jest reprezentowana binarnie przez 11111111111111111111111111111111 i dlatego będzie wymagać wiele zmian. Jeśli nie chcesz robić tak wielu przesunięć dla małych liczb ujemnych, inny sposób może być następujący:

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;
}

W Pythonie lub innym Konwertuj na bin string następnie podziel go przez '0', aby pozbyć się 0', a następnie połącz i uzyskaj długość.

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

Używając operacji łańcuchowych JS można wykonać w następujący sposób;

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

Lub

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

Musiałem grać w golfa w ruby i skończyłem z

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

Użycie:

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

Oczywiście nie wydajny, ale robi sztuczkę:)

Implementacja Ruby

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)

Dwa sposoby::

/* 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

Użycie::

    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