c++ - Next higher number with one zero bit -

today i've run problem, couldn't solve after period of time. need help

i have number n. problem find next higher number ( > n ) 1 0 bit in binary.

example: number 1 can represented in binary 1. next higher number 1 0 bit 2 - binary 10

a few other examples:
n = 2 (10), next higher number 1 0 bit 5 (101)
n = 5 (101), next higher number 6 (110)
n = 7 (111), next higher number 11 (1011)

list of 200 number:

1 1 2 10 - 1 3 11 4 100 5 101 - 1 6 110 - 1 7 111 8 1000 9 1001 10 1010 11 1011 - 1 12 1100 13 1101 - 1 14 1110 - 1 15 1111 16 10000 17 10001 18 10010 19 10011 20 10100 21 10101 22 10110 23 10111 - 1 24 11000 25 11001 26 11010 27 11011 - 1 28 11100 29 11101 - 1 30 11110 - 1 31 11111 32 100000 33 100001 34 100010 35 100011 36 100100 37 100101 38 100110 39 100111 40 101000 41 101001 42 101010 43 101011 44 101100 45 101101 46 101110 47 101111 - 1 48 110000 49 110001 50 110010 51 110011 52 110100 53 110101 54 110110 55 110111 - 1 56 111000 57 111001 58 111010 59 111011 - 1 60 111100 61 111101 - 1 62 111110 - 1 63 111111 64 1000000 65 1000001 66 1000010 67 1000011 68 1000100 69 1000101 70 1000110 71 1000111 72 1001000 73 1001001 74 1001010 75 1001011 76 1001100 77 1001101 78 1001110 79 1001111 80 1010000 81 1010001 82 1010010 83 1010011 84 1010100 85 1010101 86 1010110 87 1010111 88 1011000 89 1011001 90 1011010 91 1011011 92 1011100 93 1011101 94 1011110 95 1011111 - 1 96 1100000 97 1100001 98 1100010 99 1100011 100 1100100 101 1100101 102 1100110 103 1100111 104 1101000 105 1101001 106 1101010 107 1101011 108 1101100 109 1101101 110 1101110 111 1101111 - 1 112 1110000 113 1110001 114 1110010 115 1110011 116 1110100 117 1110101 118 1110110 119 1110111 - 1 120 1111000 121 1111001 122 1111010 123 1111011 - 1 124 1111100 125 1111101 - 1 126 1111110 - 1 127 1111111 128 10000000 129 10000001 130 10000010 131 10000011 132 10000100 133 10000101 134 10000110 135 10000111 136 10001000 137 10001001 138 10001010 139 10001011 140 10001100 141 10001101 142 10001110 143 10001111 144 10010000 145 10010001 146 10010010 147 10010011 148 10010100 149 10010101 150 10010110 151 10010111 152 10011000 153 10011001 154 10011010 155 10011011 156 10011100 157 10011101 158 10011110 159 10011111 160 10100000 161 10100001 162 10100010 163 10100011 164 10100100 165 10100101 166 10100110 167 10100111 168 10101000 169 10101001 170 10101010 171 10101011 172 10101100 173 10101101 174 10101110 175 10101111 176 10110000 177 10110001 178 10110010 179 10110011 180 10110100 181 10110101 182 10110110 183 10110111 184 10111000 185 10111001 186 10111010 187 10111011 188 10111100 189 10111101 190 10111110 191 10111111 - 1 192 11000000 193 11000001 194 11000010 195 11000011 196 11000100 197 11000101 198 11000110 199 11000111 200 11001000 

there 3 cases.

1. the number x has more 1 0 bit in binary representation. 1 of these 0 bits must "filled in" 1 obtain required result. notice numbers obtained taking x , filling in 1 or more of low-order 0 bits numerically closer x compared number obtained filling top-most 0 bit. therefore answer number x all-but-one of 0 bits filled: topmost 0 bit remains unfilled. example if x=110101001 answer 110111111. answer, find index i of topmost 0 bit of x, , calculate bitwise or of x , 2^i - 1.

c code case:

// warning: assumes x known have *some* (>1) zeros! unsigned next(unsigned x) {   unsigned topmostzero = 0;   unsigned bit = 1;   while (bit && bit <= x) {       if (!(x & bit)) topmostzero = bit;       bit <<= 1;   }   return x | (topmostzero - 1); } 

2. the number x has no 0 bits in binary. means x=2^n - 1 number n. same reasoning above, answer 2^n + 2^(n-1) - 1. example, if x=111, answer 1011.

3. the number x has 1 0 bit in binary representation. know result must strictly larger x, x not allowed answer. if x has 0 in least-significant bit, case reduces case #2. otherwise, 0 should moved 1 position right. assuming x has 0 in i-th bit, answer should have 0 in i-1-th bit. example, if x=11011, result 11101.