c - 多个位 vector ；如何找到恰好设置 n 次的位？

Question

我有四个位 vector 的集合，例如:

b1 = 00001010
b2 = 10100111
b3 = 10010010
b4 = 10111110

我想获取在给定位 vector 的 0、1、2、3 或 4 中设置的那些位的掩码。因此 m0 将是未在四个位 vector 中的任何一个中设置的位的掩码，m3 是恰好在三个位 vector 中设置的那些位的掩码，等等:

m0 = 01000000
m1 = 00000001
m2 = 00111100
m3 = 10000000
m4 = 00000010

使用按位运算符找到这些掩码的最快方法是什么？

我假设这些对 0 位和 4 位的操作最少:

m0 = ~(b1 | b2 | b3 | b4)  // 4 ops
m4 = b1 & b2 & b3 & b4     // 3 ops

对于其他选项，我不太确定我的方法有最少的操作:

m1 = ((b1 ^ b2) & ~(b3 | b4)) | (~(b1 | b2) & (b3 ^ b4)) // 9 operations
m2 = ((b1 ^ b2) & (b3 ^ b4)) | ((b1 ^ b3) & (b2 ^ b4)) | ((b1 ^ b4) & (b2 ^ b3)) // 11 operations
m3 = ((b1 ^ b2) & (b3 & b4)) | ((b1 & b2) & (b3 ^ b4)) // 7 operations

这是计算这些掩码的最快方法还是我可以做得更快(操作更少)？

在大多数情况下，我需要这些面具中的一个或几个，而不是同时需要所有面具。

(注意，实际上我将针对 64 位或 128 位 vector 执行此操作。这可能无关紧要，但我是在 32 位 x86 平台上用 C 语言执行的。)

Answer 1

所有掩码的 14 次操作。

想法是首先使用 min = x & y 和 max = x | 对位进行排序y 作为条件交换。这需要 10 次操作。然后简单地提取需要 4 次操作的掩码。

// Split in lower and upper half
var c1 = b1 & b2;
var c3 = b1 | b2;
var c2 = b3 & b4;
var c4 = b3 | b4;

// Sort within each half
var d1 = c1 & c2; // (b1 & b2) & (b3 & b4)
var d2 = c1 | c2; // (b1 & b2) | (b3 & b4)
var d3 = c3 & c4; // (b1 | b2) & (b3 | b4)
var d4 = c3 | c4; // (b1 | b2) | (b3 | b4)

// Sort middle
var e1 = d1;      // (b1 & b2) & (b3 & b4)
var e2 = d2 & d3; // ((b1 & b2) | (b3 & b4)) & ((b1 | b2) & (b3 | b4))
var e3 = d2 | d3; // ((b1 & b2) | (b3 & b4)) | ((b1 | b2) & (b3 | b4))
var e4 = d4;      // (b1 | b2) | (b3 | b4)

// Extract masks
var m4 = e1;      // (b1 & b2) & (b3 & b4)
var m3 = e2 ^ e1; // (((b1 & b2) | (b3 & b4)) & ((b1 | b2) & (b3 | b4))) ^ ((b1 & b2) & (b3 & b4))
var m2 = d3 ^ d2; // The same as e3 ^ e2, saves two operations if only m2 is required
var m1 = e4 ^ e3; // ((b1 | b2) | (b3 | b4)) ^ (((b1 & b2) | (b3 & b4)) | ((b1 | b2) & (b3 | b4)))
var m0 = ~e4;     // ~((b1 | b2) | (b3 | b4))

(代码在 C# 中，但将其转换为 C 很简单。)

---

如果您使用此代码只计算一些掩码并简单地删除不影响结果的行(一个好的编译器应该自动执行此操作)。性能也不错:

m4:3次操作
m3:9次操作
m2:7次操作
m1:9次操作
m0: 4 次操作