Python中相当于从位操作黑客C $ C $的C？ [英] Python equivalent of C code from Bit Twiddling Hacks?

问题描述

我有我试图让尽可能快一点计数方法。我想尝试从位操作黑客下面的算法，但我不知道C.什么是T型，什么是Python当量（T）〜（T）0/3的？

  

最好位的推广
  计算方法的整数
  位宽高达128（参数由
  T型）是这样的：

  V =  - （（V＆GT;＆GT; 1）及（T）〜（T）0/3）; //温度
V =（V及（T）〜（T）0/15 * 3）+（（V＆GT;＆→2）及（T）〜（T）0/15 * 3）; //温度
V =（V +（V＆GT;＆→4））及（T）〜（T）0/255 * 15; //温度
C =（T）（V *（（T）〜（T）0/255））＆GT;＆GT; （的sizeof（ⅴ） -  1）* CHAR_BIT; //计数
 

解决方案

T是一个整数类型，我假设是无符号的。由于这是C，它会被固定的宽度，很可能（但不一定）8之一，16，32，64或128片段（T）〜（T）0 反复看来，code样品中只是给出值2 ** N-1，其中N是类型T.我怀疑是code可能需要N为倍数的宽度8
正确操作。

下面是给定的code到Python，在N，T的位宽方面参数的直接转换。

 高清COUNT_SET_BITS（V，N = 128）：
    掩模=（1 <<;＆下; N） -  1    V =  - （（V＆GT;→1）及掩模// 3）
    V =（V＆放大器;掩模// 15 * 3）+（（V＆GT;→2）及掩模// 15 * 3）
    V =（V +（V＆GT;＆→4））及面膜// 255 * 15
    返回（面膜＆安培; V *（屏蔽// 255））＆GT;＆GT; （N // 8  -  1）* 8
 

注意事项：

（1）在上述将只对数字工作到2 ** 128。你也许可以概括它更大的数字，虽然。

（2）有明显的低效率：例如，掩模// 15'被计算两次。这不要紧，C，当然，因为编译器几乎肯定会做师在编译时，而不是运行时间，但Python的窥孔优化器可能不那么聪明。

（3）速度最快C法可能没有转换到Python的最快方法。对于Python的速度，你应该找了Python位操作的数量降至最低的算法。正如亚历山大·格斯勒说：简介

I have a bit counting method that I am trying to make as fast as possible. I want to try the algorithm below from Bit Twiddling Hacks, but I don't know C. What is 'type T' and what is the python equivalent of (T)~(T)0/3?

A generalization of the best bit counting method to integers of bit-widths upto 128 (parameterized by type T) is this:

v = v - ((v >> 1) & (T)~(T)0/3);      // temp 
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
c = (T)(v * ((T)~(T)0/255)) >> (sizeof(v) - 1) * CHAR_BIT; // count

解决方案

T is a integer type, which I'm assuming is unsigned. Since this is C, it'll be fixed width, probably (but not necessarily) one of 8, 16, 32, 64 or 128. The fragment (T)~(T)0 that appears repeatedly in that code sample just gives the value 2**N-1, where N is the width of the type T. I suspect that the code may require that N be a multiple of 8 for correct operation.

Here's a direct translation of the given code into Python, parameterized in terms of N, the width of T in bits.

def count_set_bits(v, N=128):
    mask = (1 << N) - 1

    v = v - ((v >> 1) & mask//3)
    v = (v & mask//15*3) + ((v >> 2) & mask//15*3)
    v = (v + (v >> 4)) & mask//255*15
    return (mask & v * (mask//255)) >> (N//8 - 1) * 8

Caveats:

(1) the above will only work for numbers up to 2**128. You might be able to generalize it for larger numbers, though.

(2) There are obvious inefficiencies: for example, 'mask//15' is computed twice. This doesn't matter for C, of course, because the compiler will almost certainly do the division at compile time rather than run time, but Python's peephole optimizer may not be so clever.

(3) The fastest C method may well not translate to the fastest Python method. For Python speed, you should probably be looking for an algorithm that minimizes the number of Python bitwise operations. As Alexander Gessler said: profile!

这篇关于Python中相当于从位操作黑客C $ C $的C？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！