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
function addOne(num) {
    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.

[ computer_science  algorithms  javascript  programming  ]
Sorting algorithms computer_science algorithms javascript programming
Raft for reaching consensus computer_science algorithms
The Rabin-Karp algorithm computer_science algorithms javascript programming
House painting problem computer_science algorithms javascript programming
Bitwise operations in Javascript algorithms javascript programming