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(log⁡n)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).