| 71 | } |
| 72 | |
| 73 | public static int getNext(int n) { |
| 74 | int c = n; |
| 75 | int c0 = 0; |
| 76 | int c1 = 0; |
| 77 | while (((c & 1) == 0) && (c != 0)) { |
| 78 | c0++; |
| 79 | c >>= 1; |
| 80 | } |
| 81 | |
| 82 | while ((c & 1) == 1) { |
| 83 | c1++; |
| 84 | c >>= 1; |
| 85 | } |
| 86 | |
| 87 | /* If c is 0, then n is a sequence of 1s followed by a sequence of 0s. This is already the biggest |
| 88 | * number with c1 ones. Return error. |
| 89 | */ |
| 90 | if (c0 + c1 == 31 || c0 + c1 == 0) { |
| 91 | return -1; |
| 92 | } |
| 93 | |
| 94 | int pos = c0 + c1; // position of right-most non-trailing zero (where the right most bit is bit 0) |
| 95 | |
| 96 | /* Flip the right-most non-trailing zero (which will be at position pos) */ |
| 97 | n |= (1 << pos); // Flip right-most non-trailing zero |
| 98 | |
| 99 | /* Clear all bits to the right of pos. |
| 100 | * Example with pos = 5 |
| 101 | * (1) Shift 1 over by 5 to create 0..0100000 [ mask = 1 << pos ] |
| 102 | * (2) Subtract 1 to get 0..0011111 [ mask = mask - 1 ] |
| 103 | * (3) Flip all the bits by using '~' to get 1..1100000 [ mask = ~mask ] |
| 104 | * (4) AND with n |
| 105 | */ |
| 106 | n &= ~((1 << pos) - 1); // Clear all bits to the right of pos |
| 107 | |
| 108 | /* Put (ones-1) 1s on the right by doing the following: |
| 109 | * (1) Shift 1 over by (ones-1) spots. If ones = 3, this gets you 0..0100 |
| 110 | * (2) Subtract one from that to get 0..0011 |
| 111 | * (3) OR with n |
| 112 | */ |
| 113 | n |= (1 << (c1 - 1)) - 1; |
| 114 | |
| 115 | return n; |
| 116 | } |
| 117 | |
| 118 | public static int getNextArith(int n) { |
| 119 | int c = n; |