文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >问答首页 >位操作:将公共部分保持在最后一个不同位的左边。

问位操作:将公共部分保持在最后一个不同位的左边。
EN

Stack Overflow用户
提问于 2014-02-03 05:54:06
回答 4查看 301关注 0票数 5

考虑用二进制语言编写的两个数字(左边是MSB)：

代码语言：javascript
复制
X = x7 x6 x5 x4 x3 x2 x1 x0

和

代码语言：javascript
复制
Y = y7 y6 y5 y4 y3 y2 y1 y0

这些数字可以有任意数量的位，但两者都是相同类型的。现在考虑一下x7 == y7，x6 == y6，x5 == y5，但是x4 != y4。

如何计算：

代码语言：javascript
复制
Z = x7 x6 x5 0 0 0 0 0

换句话说，如何有效地计算一个将公共部分保持在最后一个不同位左边的数字？

代码语言：javascript
复制
template <typename T>
inline T f(const T x, const T y) 
{
    // Something here
}

例如，对于以下方面：

代码语言：javascript
复制
x = 10100101
y = 10110010

它应该会回来

代码语言：javascript
复制
z = 10100000

注:这是为了超级计算的目的，这一操作将执行数千亿次，因此应避免逐个扫描比特。

c++
c
algorithm
optimization
bit-manipulation
EN

回答 4

Stack Overflow用户

回答已采纳

发布于 2014-02-03 06:44:42

我的答案是基于@JerryCoffin的答案。

代码语言：javascript
复制
int d = x ^ y;
d = d | (d >> 1);
d = d | (d >> 2);
d = d | (d >> 4);
d = d | (d >> 8);
d = d | (d >> 16);
int z = x & (~d);
票数 6
EN

Stack Overflow用户

发布于 2014-02-03 08:01:59

这个问题的一部分出现在位操作中：“带有or的并行后缀”或“前缀”(即，取决于您所听的是谁，低位被称为后缀或前缀)。显然，一旦您有了这样的方法，将其扩展到您想要的(如其他答案所示)是非常简单的。

不管怎样，最明显的方法是：

代码语言：javascript
复制
x |= x >> 1
x |= x >> 2
x |= x >> 4
x |= x >> 8
x |= x >> 16

但你可能并不局限于简单的运算符。

对哈斯韦尔来说，我发现的最快的方法是：

代码语言：javascript
复制
lzcnt rax, rax     ; number of leading zeroes, sets carry if rax=0
mov edx, 64
sub edx, eax
mov rax, -1
bzhi rax, rax, rdx ; reset the bits in rax starting at position rdx

其他竞争者包括：

代码语言：javascript
复制
mov rdx, -1
bsr rax, rax       ; position of the highest set bit, set Z flag if no bit
cmovz rdx, rax     ; set rdx=rax iff Z flag is set
xor eax, 63
shrx rax, rdx, rax ; rax = rdx >> rax

和

代码语言：javascript
复制
lzcnt rax, rax
sbb rdx, rdx       ; rdx -= rdx + carry (so 0 if no carry, -1 if carry)
not rdx
shrx rax, rdx, rax

但他们没那么快。

我也考虑过

代码语言：javascript
复制
lzcnt rax, rax
mov rax, [table+rax*8]

但是很难公平地比较它，因为它是唯一花费缓存空间的，它具有非本地效应。

通过对各种方法进行基准测试，导致了this question对lzcnt的一些奇怪行为的了解。

它们都依赖于一些快速的方法来确定最高集位的位置，如果你真的需要的话，你可以用一个浮点数和指数提取来实现，所以大多数平台都可以使用类似的方法。

如果移位计数等于或大于操作数大小，则给出零的移位将很好地解决这个问题。x86没有，但也许你的平台有。

如果您有一个快速的位反转指令，您可以这样做：(这并不打算是ARM asm)。

代码语言：javascript
复制
rbit r0, r0
neg r1, r0
or r0, r1, r0
rbit r0, r0
票数 3
EN

Stack Overflow用户

发布于 2014-02-03 13:20:08

比较了几种算法，得出了这样的排名：

在下面的测试中内环为1或10：

  1. 利用内置的位扫描功能。
  2. 用或或和移位填充最不重要的位( @Egor Skriptunoff的功能)。
  3. 包括一个查找表。
  4. 扫描最重要的位(@Tomas的第二个函数)。

InnerLoops = 10：

代码语言：javascript
复制
Timing 1: 0.101284
Timing 2: 0.108845
Timing 3: 0.102526
Timing 4: 0.191911

100或100以上的内环：

  1. 利用内置的位扫描功能。
  2. 包括一个查找表。
  3. 用或或和移位填充最不重要的位( @Egor Skriptunoff的功能)。
  4. 扫描最重要的位(@Tomas的第二个函数)。

InnerLoops = 100：

代码语言：javascript
复制
Timing 1: 0.441786
Timing 2: 0.507651
Timing 3: 0.548328
Timing 4: 0.593668

测试：

代码语言：javascript
复制
#include <algorithm>
#include <chrono>
#include <limits>
#include <iostream>
#include <iomanip>

// Functions
// =========

inline unsigned function1(unsigned  a, unsigned b)
{
    a ^= b;
    if(a) {
        int n = __builtin_clz (a);
        a = (~0u) >> n;
    }
    return ~a & b;
}

typedef std::uint8_t byte;
static byte msb_table[256] = {
    0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
};

inline unsigned function2(unsigned a, unsigned  b)
{
    a ^= b;
    if(a) {
        unsigned n = 0;
        if(a >> 24) n = msb_table[byte(a >> 24)] + 24;
        else if(a >> 16) n = msb_table[byte(a >> 16)] + 16;
        else if(a >> 8) n = msb_table[byte(a >> 8)] + 8;
        else n = msb_table[byte(a)];
        a = (~0u) >> (32-n);
    }
    return ~a & b;
}

inline unsigned function3(unsigned  a, unsigned  b)
{
    unsigned d = a ^ b;
    d = d | (d >> 1);
    d = d | (d >> 2);
    d = d | (d >> 4);
    d = d | (d >> 8);
    d = d | (d >> 16);
    return a & (~d);;
}

inline unsigned function4(unsigned  a, unsigned  b)
{
    const unsigned maxbit = 1u << (std::numeric_limits<unsigned>::digits - 1);
    unsigned msb = maxbit;
    a ^= b;
    while( ! (a & msb))
        msb >>= 1;
    if(msb == maxbit) return 0;
    else {
        msb <<= 1;
        msb  -= 1;
        return ~msb & b;
    }
}


// Test
// ====

inline double duration(
    std::chrono::system_clock::time_point start,
    std::chrono::system_clock::time_point end)
{
    return double((end - start).count())
        / std::chrono::system_clock::period::den;
}

int main() {
    typedef unsigned (*Function)(unsigned , unsigned);
    Function fn[] = {
        function1,
        function2,
        function3,
        function4,
    };
    const unsigned N = sizeof(fn) / sizeof(fn[0]);
    std::chrono::system_clock::duration timing[N] = {};
    const unsigned OuterLoops = 1000000;
    const unsigned InnerLoops = 100;
    const unsigned Samples = OuterLoops * InnerLoops;
    unsigned* A = new unsigned[Samples];
    unsigned* B = new unsigned[Samples];
    for(unsigned i = 0; i < Samples; ++i) {
        A[i] = std::rand();
        B[i] = std::rand();
    }
    unsigned F[N];
    for(unsigned f = 0; f < N; ++f) F[f] = f;
    unsigned result[N];
    for(unsigned i = 0; i < OuterLoops; ++i) {
        std::random_shuffle(F, F + N);
        for(unsigned f = 0; f < N; ++f) {
            unsigned g = F[f];
            auto start = std::chrono::system_clock::now();
            for(unsigned j = 0; j < InnerLoops; ++j) {
                unsigned index = i + j;
                unsigned a = A[index];
                unsigned b = B[index];
                result[g] = fn[g](a, b);
            }
            auto end = std::chrono::system_clock::now();
            timing[g] += (end-start);
        }
        for(unsigned f = 1; f < N; ++f) {
            if(result[0] != result[f]) {
                std::cerr << "Different Results\n" << std::hex;
                for(unsigned g = 0; g < N; ++g)
                    std::cout << "Result " << g+1 << ": " << result[g] << '\n';
                exit(-1);
            }
        }
    }

    for(unsigned i = 0; i < N; ++i) {
        std::cout
            << "Timing " << i+1 << ": "
            << double(timing[i].count()) / std::chrono::system_clock::period::den
            << "\n";
    }
}

编译器：

g++ 4.7.2

硬件：

英特尔核心GiB i3-2310MCPU@ 2.10GHz×4.7.7 GiB

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：

https://stackoverflow.com/questions/21520622

复制
相关文章

相似问题

领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档