反转数字的位

Question

这是一个 C++ class 用于尊重 LeetCode 讨论中的位。 https://leetcode.com/discuss/29324/c-solution-9ms-without-loop-without-calculation 例如，给定输入 43261596（以二进制表示为 00000010100101000001111010011100），return 964176192（以二进制表示为 00111001011110000010100101000000）。

有没有人可以解释一下？非常感谢！！

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        struct bs
        {
            unsigned int _00:1; unsigned int _01:1; unsigned int _02:1; unsigned int _03:1;
            unsigned int _04:1; unsigned int _05:1; unsigned int _06:1; unsigned int _07:1;
            unsigned int _08:1; unsigned int _09:1; unsigned int _10:1; unsigned int _11:1;
            unsigned int _12:1; unsigned int _13:1; unsigned int _14:1; unsigned int _15:1;
            unsigned int _16:1; unsigned int _17:1; unsigned int _18:1; unsigned int _19:1;
            unsigned int _20:1; unsigned int _21:1; unsigned int _22:1; unsigned int _23:1;
            unsigned int _24:1; unsigned int _25:1; unsigned int _26:1; unsigned int _27:1;
            unsigned int _28:1; unsigned int _29:1; unsigned int _30:1; unsigned int _31:1;
        } *b = (bs*)&n, 
        c = 
        {
              b->_31, b->_30, b->_29, b->_28
            , b->_27, b->_26, b->_25, b->_24
            , b->_23, b->_22, b->_21, b->_20
            , b->_19, b->_18, b->_17, b->_16
            , b->_15, b->_14, b->_13, b->_12
            , b->_11, b->_10, b->_09, b->_08
            , b->_07, b->_06, b->_05, b->_04
            , b->_03, b->_02, b->_01, b->_00
        };

        return *(unsigned int *)&c;
    }
};

Answer 1

将 casting 视为在内存上提供不同的布局模板。

使用此 stencil 图片，代码是 unsigned 整数内存位置上的 32 位模板布局。

因此，不是将内存视为 uint32_t，而是将内存视为 32 位。

创建了指向 32 位结构的指针。

指针被分配到与 uint32_t 变量相同的内存位置。

指针将允许对内存位置进行不同的处理。

创建了一个 32 位的临时变量（使用结构）。使用初始化列表初始化变量。
初始化列表中的位字段来自原始变量，倒序排列。

因此，在列表中：

  new bit 0 <-- old bit 31  
  new bit 1 <-- old bit 30

这种方法的基础依赖于初始化列表。作者让编译器反转这些位。

Answer 2

该解决方案使用蛮力还原位。它声明了一个位域结构（即成员后跟 :1），每个位域有 32 个位域。然后将 32 位输入视为这样的结构，方法是将输入的地址转换为指向该结构的指针。然后 c 被声明为该类型的变量，它通过恢复位的顺序来初始化。最后，将 c 表示的位域重新解释为整数，就大功告成了。

汇编器不是很有趣，如 gcc 资源管理器所示： https://goo.gl/KYHDY6

Answer 3

它并没有按顺序转换，但它只是以不同的方式查看相同的内存地址。它使用 int n 的值，但获取指向该地址的指针，对指针进行类型转换，这样，您就可以将数字解释为 32 个独立位的结构。因此，通过此结构 b 您可以访问数字的各个位。

然后，对于一个新结构 c，通过将数字的第 31 位放入输出结构 c 的第 0 位，将第 30 位放入第 1 位等，直接设置每一位。

之后，返回结构内存位置的值。

Answer 4

首先，发布的代码有一个小错误。行

return *(unsigned int *)&c;

如果 sizeof(unsigned int) 不等于 sizeof(uint32_t)，

将不是 return 准确的数字。

那一行应该是

return *(uint32_t*)&c;

关于它是如何工作的问题，我将尝试用更小的类型来解释它，uint8_t。

函数

uint8_t reverseBits(uint8_t n) {
    struct bs
    {
        unsigned int _00:1; unsigned int _01:1; unsigned int _02:1; unsigned int _03:1;
        unsigned int _04:1; unsigned int _05:1; unsigned int _06:1; unsigned int _07:1;
    } *b = (bs*)&n, 
    c = 
    {
          b->_07, b->_06, b->_05, b->_04
        , b->_03, b->_02, b->_01, b->_00
    };

    return *(uint8_t *)&c;
}

使用本地结构。本地结构定义为：

    struct bs
    {
        unsigned int _00:1; unsigned int _01:1; unsigned int _02:1; unsigned int _03:1;
        unsigned int _04:1; unsigned int _05:1; unsigned int _06:1; unsigned int _07:1;
    };

该结构有八个成员。该结构的每个成员都是一个宽度为 1 的位域。 bs 类型的对象所需的 space 是 8 位。

如果将 struct 的定义和该类型的变量分开，函数将是：

uint8_t reverseBits(uint8_t n) {
    struct bs
    {
        unsigned int _00:1; unsigned int _01:1; unsigned int _02:1; unsigned int _03:1;
        unsigned int _04:1; unsigned int _05:1; unsigned int _06:1; unsigned int _07:1;
    };

    bs *b = (bs*)&n;
    bs c =
    {
         b->_07, b->_06, b->_05, b->_04
       , b->_03, b->_02, b->_01, b->_00
    };

    return *(uint8_t *)&c;
}

现在，假设函数的输入是 0xB7，即二进制形式的 1011 0111。该行

    bs *b = (bs*)&n;

说：

获取 n ( &n )
将其视为 bs* ( (bs*)&n ) 类型的指针
将指针分配给一个变量。 (bs *b =)

通过这样做，我们能够选取 n 的每一位并使用 b 的成员获取它们的值。在该行的末尾，

b->_00的值为1
b->_01的值为0
b->_02的值为1
b->_03的值为1
b->_04的值为0
b->_05 的值为 1
b->_06的值为1
b->_07 的值为 1

声明

    bs c =
    {
         b->_07, b->_06, b->_05, b->_04
       , b->_03, b->_02, b->_01, b->_00
    };

简单地创建 c 使得 c 的位与 *b 的位相反。

行

    return *(uint8_t *)&c;

说：

取c.的地址，其值为位模式1110 1101.
将其视为 uint8_t* 类型的指针。
取消引用指针和 return 结果 uint8_t

return 是一个 uint8_t，其值从输入参数按位反转。

Answer 5

这并不完全是混淆，但一两条评论会帮助无辜者。关键在变量声明的中间，第一步要认识到这里只有一行'code'，其他都是变量声明和初始化

在声明和初始化之间我们发现：

} *b = (bs*)&n,
c =
{

这声明了一个变量 'b'，它是一个指向刚刚定义的结构 "bs" 的指针 (*)。然后它将函数参数的地址 'n'、a unit_32_t 转换为指向 bs 的类型，并将其分配给 'b'，有效地创建了一个 union 的 uint_32_t 和位数组 bs。然后声明第二个变量，一个实际的结构 bs，名为 "c"，并通过指针 'b' 对其进行初始化。 b->_31 初始化 c._00，依此类推。因此，在创建 "b" 和 "c" 之后，按此顺序，除了 return "c".

的值外，别无他法。

代码的作者和编译器知道在结构定义结束后，可以在“;”之前创建该类型或与该类型相关的变量，这就是为什么@Thomas Matthews 以， "The author is letting the compiler reverse the bits."

反转数字的位

reverse a number's bits

c++

bit-manipulation