reverse bits 的题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

reverse bits 的题目

reverse bits 的题目# Programming - 葵花宝典

s*n2007-09-21 07:09

1 楼

前不久看到有人提到这个问题。
请问这个reverse是把1变成0，0变成1 还是左右reverse?
1->0，0->1 XOR 11111111 就行了。
左右reverse该怎么弄呢？

X*r2007-09-21 07:09

2 楼

你知道数1 的个数那道题怎么做，就知道左右reverse这道题怎么做。
（回有四种写法……）

【在 s*****n 的大作中提到】

: 前不久看到有人提到这个问题。
: 请问这个reverse是把1变成0，0变成1 还是左右reverse?
: 1->0，0->1 XOR 11111111 就行了。
: 左右reverse该怎么弄呢？

s*n2007-09-21 07:09

3 楼

数1的题目很久前在一本interview书上看过，好像是挺多方法的，而且越来越出乎想象
。现在不记得了，去找来看看。

k*f2007-09-21 07:09

4 楼

jhq有

【在 s*****n 的大作中提到】

: 数1的题目很久前在一本interview书上看过，好像是挺多方法的，而且越来越出乎想象
: 。现在不记得了，去找来看看。

s*u2007-09-21 07:09

5 楼

是左右reverse吧，有奇技淫巧的，不是很记得..

【在 s*****n 的大作中提到】

: 前不久看到有人提到这个问题。
: 请问这个reverse是把1变成0，0变成1 还是左右reverse?
: 1->0，0->1 XOR 11111111 就行了。
: 左右reverse该怎么弄呢？

s*n2007-09-21 07:09

6 楼

可能我太笨了，我看了数多少个1的题目之后还是不知道改怎么左右reverse。
谁指教一下？

X*r2007-09-21 07:09

7 楼

这个……
直接方法：一位一位移位
取巧的方法：就地交换
实用的方法：查表，或部分查表和就地交换相结合。
就地交换方法如下，假设是32位无符号整数
x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
x = ((x & 0xFF00FF00) << 8) | ((x & 0x00FF00FF) >> 8);
x = ((x & 0xFFFF0000) << 16) | ((x & 0x0000FFFF) >> 16);

【在 s*****n 的大作中提到】

: 可能我太笨了，我看了数多少个1的题目之后还是不知道改怎么左右reverse。
: 谁指教一下？

s*n2007-09-21 07:09

8 楼

多谢多谢！这自己想怎么也想不出来。

【在 X****r 的大作中提到】

: 这个……
: 直接方法：一位一位移位
: 取巧的方法：就地交换
: 实用的方法：查表，或部分查表和就地交换相结合。
: 就地交换方法如下，假设是32位无符号整数
: x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
: x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
: x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
: x = ((x & 0xFF00FF00) << 8) | ((x & 0x00FF00FF) >> 8);
: x = ((x & 0xFFFF0000) << 16) | ((x & 0x0000FFFF) >> 16);