javascript - 去交错字节

Question

给定一个交错的位序列:

ABABABABABABABAB

我可以使用什么 javascript 按位运算将其转换为序列:

AAAAAAAABBBBBBBB

Answer 1

这被称为 unshuffle (另请参阅 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 位数字，您可以切掉每个掩码的左半部分并跳过最后一步。

这是一个增量交换序列，请参阅计算机编程艺术第 4A 卷，按位技巧和技术，位交换。