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. Commented Apr 18, 2016 at 5:05
  • yes but how do you explain number width with O notation ? Commented Apr 18, 2016 at 5:08
  • It's pretty standard. O(log(n)). 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. 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.