作者热门文章
- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我有四个位 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 语言执行的。)
最佳答案
所有掩码的 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 次操作
关于c - 多个位 vector ;如何找到恰好设置 n 次的位?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27037988/
我是一名优秀的程序员,十分优秀!