反转 int 中的 n 个不同的随机位

Question

我如何有效地反转 unsigned int x 中的 n 位？每个位必须随机挑选。此外，它必须只被采摘一次。 x 和返回结果之间的汉明距离必须等于 n。是否有 O(n) 的解决方案？

// rnd_engine is kind of std::minstd_rand
template< typename rnd_engine >
unsigned int invert_bits( unsigned int x, unsigned int n, rnd_engine& rndEngine ) {
   assert( n <= sizeof( x ) * 4 );
   return // your ideas?
}

Answer 1

我会执行以下操作：[将 randInt(n+1) 替换为任何函数 returns 间隔 [0,n] 中的随机整数。

1. 定义一个变量mask，其位数恰好为n：unsigned int mask = (1<<n)-1;。这是O(1)
2. 执行 Fisher-Yates Shuffle 的略微修改版本；循环 int i = 0; i<n; i++，然后在 mask 中交换 i 和 rndEngine::randInt(i+1) 的位。这是 O(n).
3. return x ^ mask。这会翻转 mask 中设置的位；这是 n 个打乱的位。这是O(1).

操作是O(n)假设randInt（或其他）是O(1)。