注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

融智技术学院

融智技术学院163分站,为广大好友提供更多的帮助

 
 
 

日志

 
 

【C语言每日一问】最快的方式了解奇偶校验  

2014-03-17 15:14:55|  分类: C语言 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题:我在用C解决二重向量。我的二重向量是unsigned long long类型的。因为大量的矢量我需要知道如果是奇偶校验,位的数是1,是偶数还是奇数。

额外的值不重要,仅仅是奇偶校验。我想知道是否有一种更快的方式比计算1的数量然后核查。我尝试着思考了一些,但没有找到。

一个简短的示例,我怎样让它工作:

  • void checkIntersection(unsigned long long int setA, unsigned long long int setB){
  •     if(isEven(setA & setB)){
  •         //do something
  •     }
  • }

 

回答:使用分开然后解决的技术:

  • uint64_t a = value;
  • a ^= (a >> 32);            // Fold the 32 MSB over the 32 LSB
  • a ^= (a >> 16);            // reducing the problem by 50%
  • a ^= (a >> 8);             // <-- this can be a good break even point
  • ..
  • return lookup_table[a & 0xff];  // 16 or 256 entries are typically good
  • ..

折叠的过程可以被应用到:

  • a ^= (a >> 1);
  • return a & 1;

在间接寻址,校验位可以被直接获取在减少了8位以后。

  • a ^= (a >> 4);

是另一种好的不用拆分的方式,因为一些处理器架构可以提供并行查找表

  • uint8_t LUT[16]

嵌入到XXM(或者NEON)寄存器。或者潜在的缓存256-entryLut的丢失可以导致超额的计算任务。通常,最好的方法处理LUT大小是给定结构中最优的。

最后一个表由16位组成,可以使用序列模拟:

  • return ((TRUTH_TABLE_FOR_PARITY) >> (a & 15)) & 1;

N上面的魔法常量,编码了奇偶校验的布尔值。

 

【C语言每日一问】最快的方式了解奇偶校验 - 融智技术学院 - 融智技术学院
  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017