C中的比特计数类似于比特乱动hack [英] Bit Counting in C similar to bit twiddling hack

问题描述

我需要创建一个例程来计算单词中不涉及循环的位(仅涉及位操作)，并且不使用大常量.

I need to make a routine that counts bits in a word that does not involve loops (only bit operations), and does not use large constants.

int x = 0xFFFFFFFF;
x += (~((x >> 1) & 0x55555555)+1);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0F0F0F0F);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003F);

这是我在摇摇欲坠的骇客上发现的，但是我可以使用的最大常量是0xFF ...不知道如何否则执行此操作.

This I found on bit twiddling hacks, but the largest constant I can use is 0xFF... Not sure how to do this otherwise.

谢谢大家.

推荐答案

例如，您可以使用常量数组COUNTS[16]，它是数字从0到15的二进制表示形式中的设置位数.然后:

You can for example use a constant array COUNTS[16] which is the number of set bits in the binary representation of numbers from 0 to 15. Then:

static inline int byte_count (int x) {
  static const int COUNTS[16] = { 0, 1, 1, 2, 1, /* fill in the rest manually */ };
  return COUNTS[x & 15] + COUNTS[x >> 4];
}

int count(int x) {
  return byte_count(x >> 24) + byte_count((x >> 16) & 255) + byte_count((x >> 8) & 255) + byte_count(x & 255);
}

没有循环，并且没有大于255的常量.

No loops and no constants larger than 255.

这篇关于C中的比特计数类似于比特乱动hack的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！