中科因仑“3+1”工程特种兵精英论坛

标题: 二进制高位到低位实现逆变 [打印本页]
作者: 伊海    时间: 2014-8-8 09:22
标题: 二进制高位到低位实现逆变
1. 编写一个函数，实现将一个32 位int 型数据的二进制高位到低位实现逆变，例如：
1101 0101 变成1010 1011。
这个题目的解决方法很多，代表性的有两种。
  1. int func(unsigned int uiData , int length)
  2. {
  3. unsigned int uiValue = 0 ;
  4. int i = 0 ;
  5. for ( i = 0 ; i < length ; i++ )
  6. {
  7. uiValue = (uiValue << 1) + (uiData & 0x01) ;
  8. uiData = uiData >> 1 ;
  9. } return uiValue ;
  10. }
复制代码

这个方法比较常见，通过移位的方法将高位到低位实现逆序。但是这个方法存在唯一的
不足之处是效率低，要进行32 次移位和运算。


作者: 伊海    时间: 2014-8-8 09:24
  1. int func (unsigned int uiData)
  2. {
  3. unsigned int uiValue = 0 ;
  4. /* 分而治之的思想*/
  5. /* 高16 位和低16 互换*/
  6. uiValue = ((uiData >> 16)&0x0000ffff) |
  7. ((uiData << 16)&0xffff0000);
  8. /*高低16 位中的高低8 位互换*/
  9. uiValue = ((uiValue >> 8)&0x00ff00ff) |
  10. ((uiValue << 8)&0xff00ff00);
  11. /*8 位中的高低4 位互换*/
  12. uiValue = ((uiValue >> 4)&0x0f0f0f0f) |
  13. ((uiValue << 4)&0xf0f0f0f0);
  14. /*4 位中的高低2 位互换*/
  15. uiValue = ((uiValue >> 2)&0x33333333) |
  16. ((uiValue << 2)&0xcccccccc);
  17. /*2 位中的高低位互换*/
  18. uiValue = ((uiValue >> 1)&0x55555555) |
  19. ((uiValue << 1)&0xaaaaaaaa);
  20. return uiValue ;
复制代码
这个程序只需要位操作5 次，就能实现高位到低位的逆序。我们逐句程序分析一下。
假设uiData = 1100 0101 0101 1100 1100 0101 0101 1111。执行完成下面这句
程序，
/* 高16 位和低16 互换*/
uiValue = ((uiData >> 16)&0x0000ffff) | ((uiData << 16)&0xffff0000);
得到1100 0101 0101 1111 1100 0101 0101 1100，也就是高16 位和低16
位互换。

作者: 伊海    时间: 2014-8-8 09:26
执行完成：
/*高低16 位中的高低8 位互换*/
uiValue = ((uiValue >> 8)&0x00ff00ff) | ((uiValue << 8)&0xff00ff00);
得到0101 1111 1100 0101 0101 1100 1100 0101，也就是高低16 位中高8
位和低8 位互换。

执行完成：
/*8 位中的高低4 位互换*/
uiValue = ((uiValue >> 4)&0x0f0f0f0f) | ((uiValue << 4)&0xf0f0f0f0);
得到1111 0101 0101 1100 1100 0101 0101 1100，也就是从高位起，每8 位
段的高4 位和低4 位完成互换。

执行完成：
/*4 位中的高低2 位互换*/
uiValue = ((uiValue >> 2)&0x33333333) | ((uiValue << 2)&0xcccccccc);
得到1111 0101 0101 0011 0011 0101 0101 0011，也就是从高位起，每4 位
段的高2 位和低2 位完成互换。

执行完成：
/*2 位中的高低位互换*/
uiValue = ((uiValue >> 1)&0x55555555) | ((uiValue << 1)&0xaaaaaaaa);
得到1111 1010 1010 0011 0011 1010 1010 0011。也就是从高位起，每2 位
段的高1 位和低1 位完成互换。和原始数据1100 0101 0101 1100 1100 0101 0101
1111 进行对比，逆序。

作者: lucky80204    时间: 2014-8-8 09:52
受教了，我长知识了
作者: 还你一世界    时间: 2014-8-8 10:01
领教了，看似简单但是含义丰富
作者: hxh    时间: 2014-8-8 12:30
{:soso_e179:}顶你
作者: 墨奚    时间: 2014-8-10 14:34
高手都是在考虑优化



欢迎光临 中科因仑“3+1”工程特种兵精英论坛 (http://bbs.enlern.com/) Powered by Discuz! X3.4