Tag: 汉明重量

该算法如何计算32位整数中的设置位数？

int SWAR(unsigned int i) { i = i – ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; } 我已经看到这个代码计算32位整数中的位数等于1 ，我注意到它的性能优于__builtin_popcount但我无法理解它的工作方式。 有人可以详细解释这段代码的工作原理吗？

基于汉明重量的索引

假设我们有一个整数的bitsize n=4; 我所描述的问题是如何根据汉明权重及其知道bitsize值将数字索引到数组位置。 例如，一个包含16个用于bitsize 4的元素的数组将会/看起来像这样： |0|1|2|4|8|3|5|6|9|10|12|7|11|13|14|15| 元素按其汉明重量（必要）分组，并根据大小（不必要）排序。 只要你可以采取例如3（0011）做一些操作并取回索引5,5（0101） – > 6等，就不需要排序。 将出现n位的所有组合，并且不会重复。 例如， 3 bitsize将具有数组： |0|1|2|4|3|5|6|7| 我最好有一个没有循环的解决方案。 或任何讨论simillar解决方案的论文。 或者最后只是抛出任何关于如何做到这一点的想法。