I got asked this question in a code interview and I wanted to make sure my answer was good. Without the pressure of being in an interview I see the problem more clearly and the problem seems pretty easy now.

Lets look at the basics of adding in binary:

``````1
2
3
4
0         1       1
+0        +0      +1
---       ---     ---
0         1      10
``````

Now lets look at how it looks to add 1 to a few numbers:

``````1
2
3
4
1000       1111      10011
+1         +1         +1
----      -----      -----
1001      10000      10100
``````

You probably noticed a pattern from those examples. The way you add 1 to a number is by finding the rightmost 0, turning it to 1 and then turning all numbers to the right to 0. Here is an example of an implementation:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var pos = 1;

// Find the first 0
// Parentheses are important here
// !== has higher precedence than &
while ((pos & num) !== 0) {
pos = pos << 1;
}

// Switch the 0 to a 1
num = num | pos;

// Switch all 1s to the right
pos = pos >> 1;
while (pos !== 0) {
num = num ^ pos;
pos = pos >> 1;
}

return num;
}
``````

The complexity is O(n) where n is the number of bits in the number. For the worst case scenario there will only be 1s in the number and you will have to go through all of the bits.