Title address
Leetcode-cn.com/problems/re…
Topic describes
Inverts the binary bits of the given 32-bit unsigned integer.
Tip:
Note that in some languages, such as Java, there are no unsigned integer types. In this case, both input and output will be specified as signed integer types, and should not affect your implementation, because the internal binary representation of an integer is the same whether it is signed or unsigned. In Java, the compiler uses binary complement notation to represent signed integers. Therefore, in example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.
Answer key
Two exchange
Swap the high and the corresponding low directly
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int low = 0;
int high = 0;
int result = 0;
for (int i = 0; i < 16; i++) {
low = n & (1 << i);
high = n & (1< < (32 - i -1));
result = result | (low << (32 - i - 1 - i));
result = result | (high >>> (32 - i - 1 - i));
}
returnresult; }}Copy the code
Complexity analysis
-
Time complexity: O(logn)O(\log n)O(logn), NNN is integer.size
-
Space complexity: O(1)O(1)O(1).
Divide and conquer method
First half, swap, and then swap each half, until only one digit can be swapped
The JDK is also implemented this way
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
n = ((n & 0x0000ffff) < <16 ) | ((n & 0xffff0000) > > >16);
n = ((n & 0x00ff00ff) < <8 ) | ((n & 0xff00ff00) > > >8 );
n = ((n & 0x0f0f0f0f) < <4 ) | ((n & 0xf0f0f0f0) > > >4 );
n = ((n & 0x33333333) < <2 ) | ((n & 0xCCCCCCCC) > > >2 );
n = ((n & 0x55555555) < <1 ) | ((n & 0xAAAAAAAA) > > >1 );
returnn; }}Copy the code
Complexity analysis
-
Time complexity: O(1)O(1)O(1)
-
Space complexity: O(1)O(1)O(1).