Wie finde ich die Anzahl der Einsen in einer Binärzahl in O (1)?
Ich weiß, dass dies schon einmal gefragt wurde, aber ich schaue mir diese spezielle Lösung anHier:
int BitCount(unsigned int u)
{
unsigned int uCount;
uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}
Wie funktioniert es?
Gibt es hier irgendwelche Einschränkungen?
Theoretisch ist es möglich, die Antwort in konstanter Zeit zu finden? Ich meine, nicht wahr?haben die Bits durchlaufen, um zu zählen?