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

1 Answer 1

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 and acknowledge you have read our privacy policy.

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