| 146 | } |
| 147 | |
| 148 | public static int getPrev(int n) { |
| 149 | int temp = n; |
| 150 | int c0 = 0; |
| 151 | int c1 = 0; |
| 152 | while ((temp & 1) == 1) { |
| 153 | c1++; |
| 154 | temp >>= 1; |
| 155 | } |
| 156 | |
| 157 | /* If temp is 0, then the number is a sequence of 0s followed by a sequence of 1s. This is already |
| 158 | * the smallest number with c1 ones. Return -1 for an error. |
| 159 | */ |
| 160 | if (temp == 0) { |
| 161 | return -1; |
| 162 | } |
| 163 | |
| 164 | while (((temp & 1) == 0) && (temp != 0)) { |
| 165 | c0++; |
| 166 | temp >>= 1; |
| 167 | } |
| 168 | |
| 169 | int p = c0 + c1; // position of right-most non-trailing one (where the right most bit is bit 0) |
| 170 | |
| 171 | /* Flip right-most non-trailing one. |
| 172 | * Example: n = 00011100011. |
| 173 | * c1 = 2 |
| 174 | * c0 = 3 |
| 175 | * pos = 5 |
| 176 | * |
| 177 | * Build up a mask as follows: |
| 178 | * (1) ~0 will be a sequence of 1s |
| 179 | * (2) shifting left by p + 1 will give you 11.111000000 (six 0s) |
| 180 | * (3) ANDing with n will clear the last 6 bits |
| 181 | * n is now 00011000000 |
| 182 | */ |
| 183 | n &= ((~0) << (p + 1)); // clears from bit p onwards (to the right) |
| 184 | |
| 185 | /* Create a sequence of (c1+1) 1s as follows |
| 186 | * (1) Shift 1 to the left (c1+1) times. If c1 is 2, this will give you 0..001000 |
| 187 | * (2) Subtract one from that. This will give you 0..00111 |
| 188 | */ |
| 189 | int mask = (1 << (c1 + 1)) - 1; // Sequence of (c1+1) ones |
| 190 | |
| 191 | /* Move the ones to be right up next to bit p |
| 192 | * Since this is a sequence of (c1+1) ones, and p = c1 + c0, we just need to |
| 193 | * shift this over by (c0-1) spots. |
| 194 | * If c0 = 3 and c1 = 2, then this will look like 00...0011100 |
| 195 | * |
| 196 | * Then, finally, we OR this with n. |
| 197 | */ |
| 198 | n |= mask << (c0 - 1); |
| 199 | |
| 200 | return n; |
| 201 | } |
| 202 | |
| 203 | public static int getPrevArith(int n) { |
| 204 | int temp = n; |