|
| 1 | +packageeasy; |
| 2 | +/**190. Reverse Bits QuestionEditorial Solution My Submissions |
| 3 | +Total Accepted: 72198 |
| 4 | +Total Submissions: 245079 |
| 5 | +Difficulty: Easy |
| 6 | +Reverse bits of a given 32 bits unsigned integer. |
| 7 | +
|
| 8 | +For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000). |
| 9 | +
|
| 10 | +Follow up: |
| 11 | +If this function is called many times, how would you optimize it? |
| 12 | +
|
| 13 | +Related problem: Reverse Integer*/ |
| 14 | +publicclassReverseBits { |
| 15 | +/**This post: http://stackoverflow.com/questions/2811319/difference-between-and |
| 16 | + * gives a good explanation between logical right shift: ">>>" and arithmetic right shift: ">>". |
| 17 | + * Basically, ">>" preserves the most left bit and treats it as the sign for this number, |
| 18 | + * e.g. -2 represented in 8 bits is 11111110, thus -2 >> 1 will become 11111111, i.e. -1 |
| 19 | + * notice its sign bit (the most left one bit) is preserved |
| 20 | + * However, logical right shift ">>>" doesn't care about the first bit on the most left, |
| 21 | + * it simply shifts every bit to the right. |
| 22 | + * e.g. -2 >>> 1 would become 1111111111111111111111111111111, i.e. 2147483647*/ |
| 23 | + |
| 24 | + |
| 25 | +// you need treat n as an unsigned value |
| 26 | +//inspired by this solution: https://discuss.leetcode.com/topic/9764/java-solution-and-optimization |
| 27 | +publicintreverseBits(intn) { |
| 28 | +intres =0; |
| 29 | +for(inti =0;i <32;i++){ |
| 30 | +res +=n&1;//get the most right bit each time |
| 31 | +n =n >>>1;//do UN-signed right shift by 1 each time |
| 32 | +if(i <31)res =res <<1;//shift this number to the left by 1 each time, so that eventually, this number is reversed |
| 33 | + } |
| 34 | +returnres; |
| 35 | + } |
| 36 | + |
| 37 | +//follow-up: if this function is called many times, how to improve it? |
| 38 | +//Divide the integer into 4 bytes, reverse each byte and then combine them into one in the end, use cache to store the reversed results for reuse if possible. |
| 39 | + |
| 40 | +publicstaticvoidmain(String...strings){ |
| 41 | +System.out.println(Integer.toBinaryString(4)); |
| 42 | +ReverseBitstest =newReverseBits(); |
| 43 | +intn =1; |
| 44 | +System.out.println(test.reverseBits(n)); |
| 45 | +System.out.println(Integer.parseInt("11000",2)); |
| 46 | +System.out.println(Integer.parseInt("00011",2)); |
| 47 | +// System.out.println(-2 >>> 1); |
| 48 | +// System.out.println(Integer.toBinaryString(-2 >>> 1)); |
| 49 | +// System.out.println(Integer.toBinaryString(-2)); |
| 50 | +System.out.println(Integer.toBinaryString(-1)); |
| 51 | + |
| 52 | +System.out.println(Integer.toBinaryString(6)); |
| 53 | + } |
| 54 | +} |