I'm trying to understand big O with the bitwise operations. I have 2 functions those are solving the same question from different perspective.
num1BitsSecondSolution
starts to shift the number right until number is 0. So Complexity looks like = O(width(n)) but how could I notate width
?
num1BitsThirdSolution
it is more complex to calculate it's respected complexity because it just do number = number & (number - 1)
which is based on number's initial bit representation form. Example : If there are 4 "1" bits in the number then complexity is O(4)
so how could I explain these in Big O ?
function num1BitsSecondSolution($number)
{
if ($number <= 0) {
return 0;
}
for ($c = 0; $number; $number >>= 1) {
$c += $number & 1;
}
return $c;
}
function num1BitsThirdSolution($number)
{
if ($number <= 0) {
return 0;
}
for ($c = 0; $number; $c++) {
$number &= $number - 1;
}
return $c;
}
log base 2
. That will give you (approximately) the left most digit position.O(log(n))
.