0

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;
}
  • "Number Width" you could try log base 2. That will give you (approximately) the left most digit position. – ArTs Apr 18 '16 at 5:05
  • yes but how do you explain number width with O notation ? – FZE Apr 18 '16 at 5:08
  • It's pretty standard. O(log(n)). – ArTs Apr 18 '16 at 5:10
  • I understand O(log(n)) but I didn't realize log(n)'s complexity itself o(log(n)) interesting. – FZE Apr 18 '16 at 5:28
1

O(log n) where n is the size of the number. The two functions have the same complexity, since they each perform an operation pr bit. The second example may be faster depending on the actual bits, but big-O notation is calculated for the worst case, which is this case would be a number with only 1-bits.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.