java - 反转 int 中的所有位并返回 int

Question

当我们反转整数 1 的所有位时，应该返回什么整数？我们如何用 Java 代码做到这一点？

不应使用 java 内置函数。不应使用字符串反转、转换为字符串等。仅允许按位运算。

import java.util.*;
import java.lang.*;
import java.io.*;

class BitReverseInt
{
    public static void main (String[] args) throws java.lang.Exception{
        System.out.println(reverser(1));
    }

    public static int reverser(int given){
          int input = given;
          int temp = 0;
          int output = 0;
          while(input > 0){
            output = output << 1;
            temp = input & 1;
            input = input >> 1;
            output = output | temp;
          }

          return output;
    }
}

Answer 1

位反转可以通过交换相邻的单个位，然后交换相邻的 2 位字段，然后是 4 位字段，依此类推，如下所示。这五个赋值语句可以按任意顺序执行。

/********************************************************
 * These are the bit masks used in the bit reversal process

   0x55555555 = 01010101010101010101010101010101
   0xAAAAAAAA = 10101010101010101010101010101010
   0x33333333 = 00110011001100110011001100110011
   0xCCCCCCCC = 11001100110011001100110011001100
   0x0F0F0F0F = 00001111000011110000111100001111
   0xF0F0F0F0 = 11110000111100001111000011110000
   0x00FF00FF = 00000000111111110000000011111111
   0xFF00FF00 = 11111111000000001111111100000000
   0x0000FFFF = 00000000000000001111111111111111
   0xFFFF0000 = 11111111111111110000000000000000

 */

    uint x = 23885963;    // 00000001011011000111100010001011

    x = (x & 0x55555555) <<  1 | (x & 0xAAAAAAAA) >>  1; 
    x = (x & 0x33333333) <<  2 | (x & 0xCCCCCCCC) >>  2; 
    x = (x & 0x0F0F0F0F) <<  4 | (x & 0xF0F0F0F0) >>  4; 
    x = (x & 0x00FF00FF) <<  8 | (x & 0xFF00FF00) >>  8; 
    x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;

    // result x == 3508418176   11010001000111100011011010000000

通过查看每个中间结果，您可以了解正在发生的情况。

希望这能为您提供在头脑中解决问题所需的信息。 John Doe 的答案将步骤 4 和 5 合并为一个表达式。这适用于大多数机器。