C：位反转逻辑 [英] c: bit reversal logic

问题描述

我在看下面的位反转code和只是想知道一个人如何想出这类事情。 （来源： http://www.cl.cam.ac.uk/~ am21 / hakmemc.html ）

I was looking at the below bit reversal code and just wondering how does one come up with these kind of things. (source : http://www.cl.cam.ac.uk/~am21/hakmemc.html)

/* reverse 8 bits (Schroeppel) */
unsigned reverse_8bits(unsigned41 a) {
  return ((a * 0x000202020202)  /* 5 copies in 40 bits */
             & 0x010884422010)  /* where bits coincide with reverse repeated base 2^10 */
                                /* PDP-10: 041(6 bits):020420420020(35 bits) */
             % 1023;            /* casting out 2^10 - 1's */
}

有人能解释什么呢评论，其中位反向重复基地2 ^ 10不谋而合是什么意思？
还怎么做的1023％拉出培训相关的位？有什么总体思路在这？

Can someone explain what does comment "where bits coincide with reverse repeated base 2^10" mean? Also how does "%1023" pull out the relevent bits? Is there any general idea in this?

推荐答案

这是你问一个很广泛的问题。

It is a very broad question you are asking.

下面是的解释是什么％1023 约摸：你知道如何计算 N％9 像总结基10重新$ p $ 的psentation的数字ñ？例如，52％9 = 7 = 5 + 2。
在你的问题中code是做同样的事情，与1023 = 1024 - 而不是1 9 = 10 - 1，使用操作％1023 收集多个结果已经计算独立地为大量的10位片

Here is an explanation of what % 1023 might be about: you know how computing n % 9 is like summing the digits of the base-10 representation of n? For instance, 52 % 9 = 7 = 5 + 2. The code in your question is doing the same thing with 1023 = 1024 - 1 instead of 9 = 10 - 1. It is using the operation % 1023 to gather multiple results that have been computed "independently" as 10-bit slices of a large number.

这是一个线索的开始，因为如何常数 0x000202020202 和 0x010884422010 的选择：他们做宽整数操作对大量的10位分片操作为独立简单的操作

And this is the beginning of a clue as to how the constants 0x000202020202 and 0x010884422010 are chosen: they make wide integer operations operate as independent simpler operations on 10-bit slices of a large number.

这篇关于C：位反转逻辑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！