1부터 2진수로 변환하여 테스트 케이스를 만들어보면 다음과 같습니다.

1(1)
2(10)

2(10)
3(11)

3(11)
5(101)

4(100)
5(101)

5(101)
6(110)

6(110)
7(111)

7(111)
11(1011)

8(1000)
9(1001)

9(1001)
10(1010)

10(1010)
11(1011)

11(1011)
13(1101)
...

예를들어

38(100111) 의 답은 무엇일까요?
40(101000) 이 아닌 43(101011) 입니다.

감이 오시나요?

규칙을 찾아보면

맨 오른쪽부터 0을 만나게 되면 .. (1)
해당 비트를 1로 바꿔주고 .. (2)
그 이전의 비트는 0으로 바꿔주면 되겠죠. .. (3)

100111 에서 4번째에서 처음으로 0이 나오게 됩니다. (1)번 과정

그러면 4번째 비트를 1로 바꾸면 101111 로 바뀌게 됩니다. (2)번 과정

이후 4번째에 0이 나왔으니까 3번째 1을 0으로 바꾸기만 하면 됩니다.
101111 -> 101011 이 됩니다. (3)번 과정

(1) 과정은 AND 연산을 통해
(2) 과정은 OR 연산을 통해
(2) 과정은 XOR 연산을 통해 가능합니다.

(2번 과정에서 만약 4(100) 처럼 0번째 인덱스가 0이라면,
-1 번째 인덱스를 1로 바꿀수 없으니 무시해야합니다.
근데 어차피 0을 2로 나눠도 0이므로 연산에 영향을 주진 않습니다.)

코드로 확인해보면

다음은 1부터 비트를 왼쪽으로 이동하면서 0을 찾으면
(1), (2), (3) 과정을 해주는 코드입니다.

for(long i=1;;i<<=1) if((num&i)==0) { // (1)
    num|=i; // (2)
    num^=(i>>1); // (3)
    break;
}

근데 비트 연산이 조금 낯설다 싶으면 (2),(3) 과정은 그냥 더해주고 빼줘도 됩니다.
100111 에서
001000 을 더하고
000100 을 빼면 됩니다.

for(long i=1;;i<<=1) if((num&i)==0) { // (1)
    num+=i; // (2)
    num-=(i>>1); // (3)
    break;
}

쉬프트 연산도 곱하기와 나누기로 바꿔주면 다음과 같습니다.

for(long i=1;;i*=2) if((num&i)==0) { // (1)
    num+=i; // (2)
    num-=(i/2); // (3)
    break;
}

아래로 내려보시면 제출한 코드도 같이 참고가능합니다.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.