给定的交错位序列为:
ABABABABABABABAB
我可以使用什么javascript逐位操作将其转换为以下序列:
AAAAAAAABBBBBBBB
这被称为取消洗牌(另请参阅Hacker‘s Delight 7.2,洗牌位)。
Hacker‘s Delight中给出的算法是:
t = (x ^ (x >> 1)) & 0x22222222; x = x ^ t ^ (t << 1);
t = (x ^ (x >> 2)) & 0x0C0C0C0C; x = x ^ t ^ (t << 2);
t = (x ^ (x >> 4)) & 0x00F000F0; x = x ^ t ^ (t << 4);
t = (x ^ (x >> 8)) & 0x0000FF00; x = x ^ t ^ (t << 8);
这些右移可以是逻辑的,也可以是算术的,带有掩码的AND确保受该差异影响的位无论如何都不会出现在t
中。
这适用于32位数字,对于16位数字,您可以剪掉每个掩码的左半部分,然后跳过最后一步。
这是一个delta交换序列,请参阅计算机编程艺术第4A卷,比特技巧和技术,比特交换。
如果这个算法对你有好处,请查看它:
function deinterlace(input) {
var maskOdd = 1;
var maskEven = 2;
var result = 0;
for (var i = 0; i < 8; i++) {
result = result << 1;
if(maskOdd & input) {
result += 1;
}
maskOdd = maskOdd << 2;
}
for (var j = 0; j < 8; j++) {
result = result << 1;
if(maskEven & input) {
result += 1;
console.log(result);
}
}
return result;
}
工作小提琴。