给定两个 32 位数字 N 和 M，以及两个位位置 i 和 j。写一个方法让 N 中 i 和 j 之间的所有位都等于 M
Given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M
You are given two 32-bit numbers, N and M, and two bit positions, i
and j. Write a method to set all bits between i and j in N equal to M
(e.g., M becomes a substring of N located at i and starting at j).
EXAMPLE: Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N =
10001010100
这个问题来自 Cracking the Coding 面试。我能够使用以下 O(j - i) 算法解决它：
def set_bits(a, b, i, j):
if not b: return a
while i <= j:
if b & 1 == 1:
last_bit = (b & 1) << i
a |= last_bit
else:
set_bit = ~(1 << i)
a &= set_bit
b >>= 1
i += 1
return a
作者给出了这个O(1)的算法作为解决方案：
def update_bits(n, m, i, j):
max = ~0 # All 1s
# 1s through position j, then zeroes
left = max - ((1 << j) - 1)
# 1s after position i
right = ((1 << i) - 1)
# 1’s, with 0s between i and j
mask = left | right
# Clear i through j, then put m in there
return (n & mask) | (m << i)
我注意到对于某些测试用例，作者的算法似乎输出了错误的答案。例如，对于 N = 488、M = 5、i = 2、j = 6，它输出 468。当输出应该是 404 时，就像我的 O(j - i) 算法一样。
问题：有没有办法得到适用于所有情况的恒定时间算法？
我认为所提出的解决方案有一个错误。
应该是：
def update_bits(n, m, i, j):
max = ~0 # All 1s
# 1s through position j + 1, then zeroes
left = max - ((1 << (j + 1)) - 1)
# 1s after position i
right = ((1 << i) - 1)
# 1’s, with 0s between i and j
mask = left | right
# Clear i through j, then put m in there
return (n & mask) | (m << i)
因为它说我们应该从j开始填充到i，所以我们也需要清除位j。结果是预期的 404。
更进一步，如果 m 超过 (j - i + 1) 位，我们需要更改 return 语句：
return (n & mask) | ((m << i) & ~mask)
我认为算法的作者假定 j 的界限（在你的例子中是六个）是 exclusive；这归结为从 2 到 6 的范围是否应该包括 6 的问题（在 Python 中不是这种情况）。也就是说，如果算法修改为：
def update_bits(n, m, i, j):
max = ~0 # All 1s
# 1s through position j, then zeroes
left = max - ((1 << (j+1)) - 1)
# 1s after position i
right = ((1 << i) - 1)
# 1’s, with 0s between i and j
mask = left | right
# Clear i through j, then put m in there
return (n & mask) | (m << i)
有效。
尽管如此，您可以通过以下方式加快速度：
def update_bits(n, m, i, j):
# 1s through position j, then zeroes
left = (~0) << (j+1)
# 1s after position i
right = ((1 << i) - 1)
# 1’s, with 0s between i and j
mask = left | right
# Clear i through j, then put m in there
return (n & mask) | (m << i)
在这个例子中，我们只是将那些移出寄存器。
注意你自己的算法有误，万一b = 0，这并不意味着你可以简单地return a，因为对于那个范围，这些位应该被清除。假设 a = '0b1011001111101111' 和 b = '0b0' 和 i 和 j 分别是 6 和 8，人们期望结果是 '0b1011001000101111'。因此算法应该是：
def set_bits(a, b, i, j):
while i <= j:
if b & 1 == 1:
last_bit = (b & 1) << i
a |= last_bit
else:
set_bit = ~(1 << i)
a &= set_bit
b >>= 1
i += 1
return a
如果我进行此修改并使用 10'000'000 个随机输入测试程序，两种算法总是产生相同的结果：
for i in range(10000000):
m = randint(0,65536)
i = randint(0,15)
j = randint(i,16)
n = randint(0,2**(j-i))
if set_bits(m,n,i,j) != update_bits(m,n,i,j):
print((bin(m),bin(n),i,j,bin(set_bits(m,n,i,j)),bin(update_bits(m,n,i,j)))) #This line is never printed.
当然这不是证明这两种算法是等价的（也许它们之间存在一个微小的差异），但我非常有信心对于有效输入（i 和 j 正，i < j，等等）两者应该总是产生相同的结果。
创建掩码 m 已为 <i,j>
之间的所有位设置位
您可以使用算术左移来创建 2 的幂，利用 2 减 1 的幂是所有设置位都达到指数 1 的数字
所以设置所有位 <0,j> 然后清除位直到 i-1
将位从 M 复制到 N
所以使用 m 清除 N 中的位，然后复制 M 位而不是它们。不要忘记将 M 左移 i 以匹配您的情况...
在 C++ 中（抱歉不要使用 python）是 O(1) 这样的：
DWORD bitcopy(DWORD N,DWORD M,int i,int j)
{
DWORD m;
// set bits <0..j>
m =(2<<j)-1;
// clears <0..i)
if (i) m^=(2<<(i-1))-1;
// clear space for copied bits
N&=0xFFFFFFFF-m;
// copy bits M->N
N|=(M<<i)&m;
return N;
}
您也可以使用 LUT 代替 m 的 i,j 位部分...因为您有 32 位数字，它只需要 32 或64 个数字，如果您对移位不满意...
这个版本似乎也能正常工作，前提是i <= j
def set_bits(n, m, i, j):
mask = (1 << (j + 1)) - (1 << i)
return n & ~mask | (m << i) & mask
它很简单，一旦你知道你必须做什么，你就可以自己实现它...
这里是 32 位示例：
给定：
n = 10000000000000000000000000000000
米=10101
i=2 , j=6
第 1 步：创建遮罩 ->
int x=(~0); //All Ones 11111111111111111111111111111111
int left=(1<<i)-1; // 11
int right=x-((1<<j)-1); // 11111111111111111111111111000000
int mask=left | right; // 11111111111111111111111111000011
第 2 步：清除给定数字中 i 和 j 之间的位 'n' ->
int cleared = n & mask; // 10000000000000000000000000000000
第 3 步：将 m 放入 n 中 i 和 j 之间（清除位）->
int ans= cleared | m<<i; 10000000000000000000000001010100
You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j). EXAMPLE: Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N = 10001010100
这个问题来自 Cracking the Coding 面试。我能够使用以下 O(j - i) 算法解决它：
def set_bits(a, b, i, j):
if not b: return a
while i <= j:
if b & 1 == 1:
last_bit = (b & 1) << i
a |= last_bit
else:
set_bit = ~(1 << i)
a &= set_bit
b >>= 1
i += 1
return a
作者给出了这个O(1)的算法作为解决方案：
def update_bits(n, m, i, j):
max = ~0 # All 1s
# 1s through position j, then zeroes
left = max - ((1 << j) - 1)
# 1s after position i
right = ((1 << i) - 1)
# 1’s, with 0s between i and j
mask = left | right
# Clear i through j, then put m in there
return (n & mask) | (m << i)
我注意到对于某些测试用例，作者的算法似乎输出了错误的答案。例如，对于 N = 488、M = 5、i = 2、j = 6，它输出 468。当输出应该是 404 时，就像我的 O(j - i) 算法一样。
问题：有没有办法得到适用于所有情况的恒定时间算法？
我认为所提出的解决方案有一个错误。
应该是：
def update_bits(n, m, i, j):
max = ~0 # All 1s
# 1s through position j + 1, then zeroes
left = max - ((1 << (j + 1)) - 1)
# 1s after position i
right = ((1 << i) - 1)
# 1’s, with 0s between i and j
mask = left | right
# Clear i through j, then put m in there
return (n & mask) | (m << i)
因为它说我们应该从j开始填充到i，所以我们也需要清除位j。结果是预期的 404。
更进一步，如果 m 超过 (j - i + 1) 位，我们需要更改 return 语句：
return (n & mask) | ((m << i) & ~mask)
我认为算法的作者假定 j 的界限（在你的例子中是六个）是 exclusive；这归结为从 2 到 6 的范围是否应该包括 6 的问题（在 Python 中不是这种情况）。也就是说，如果算法修改为：
def update_bits(n, m, i, j):
max = ~0 # All 1s
# 1s through position j, then zeroes
left = max - ((1 << (j+1)) - 1)
# 1s after position i
right = ((1 << i) - 1)
# 1’s, with 0s between i and j
mask = left | right
# Clear i through j, then put m in there
return (n & mask) | (m << i)
有效。
尽管如此，您可以通过以下方式加快速度：
def update_bits(n, m, i, j):
# 1s through position j, then zeroes
left = (~0) << (j+1)
# 1s after position i
right = ((1 << i) - 1)
# 1’s, with 0s between i and j
mask = left | right
# Clear i through j, then put m in there
return (n & mask) | (m << i)
在这个例子中，我们只是将那些移出寄存器。
注意你自己的算法有误，万一b = 0，这并不意味着你可以简单地return a，因为对于那个范围，这些位应该被清除。假设 a = '0b1011001111101111' 和 b = '0b0' 和 i 和 j 分别是 6 和 8，人们期望结果是 '0b1011001000101111'。因此算法应该是：
def set_bits(a, b, i, j):
while i <= j:
if b & 1 == 1:
last_bit = (b & 1) << i
a |= last_bit
else:
set_bit = ~(1 << i)
a &= set_bit
b >>= 1
i += 1
return a
如果我进行此修改并使用 10'000'000 个随机输入测试程序，两种算法总是产生相同的结果：
for i in range(10000000):
m = randint(0,65536)
i = randint(0,15)
j = randint(i,16)
n = randint(0,2**(j-i))
if set_bits(m,n,i,j) != update_bits(m,n,i,j):
print((bin(m),bin(n),i,j,bin(set_bits(m,n,i,j)),bin(update_bits(m,n,i,j)))) #This line is never printed.
当然这不是证明这两种算法是等价的（也许它们之间存在一个微小的差异），但我非常有信心对于有效输入（i 和 j 正，i < j，等等）两者应该总是产生相同的结果。
创建掩码
之间的所有位设置位m已为<i,j>您可以使用算术左移来创建 2 的幂，利用 2 减 1 的幂是所有设置位都达到指数 1 的数字 所以设置所有位
<0,j>然后清除位直到i-1将位从
M复制到N所以使用
m清除N中的位，然后复制M位而不是它们。不要忘记将M左移i以匹配您的情况...
在 C++ 中（抱歉不要使用 python）是 O(1) 这样的：
DWORD bitcopy(DWORD N,DWORD M,int i,int j)
{
DWORD m;
// set bits <0..j>
m =(2<<j)-1;
// clears <0..i)
if (i) m^=(2<<(i-1))-1;
// clear space for copied bits
N&=0xFFFFFFFF-m;
// copy bits M->N
N|=(M<<i)&m;
return N;
}
您也可以使用 LUT 代替 m 的 i,j 位部分...因为您有 32 位数字，它只需要 32 或64 个数字，如果您对移位不满意...
这个版本似乎也能正常工作，前提是i <= j
def set_bits(n, m, i, j):
mask = (1 << (j + 1)) - (1 << i)
return n & ~mask | (m << i) & mask
它很简单，一旦你知道你必须做什么，你就可以自己实现它...
这里是 32 位示例：
给定：
n = 10000000000000000000000000000000
米=10101
i=2 , j=6
第 1 步：创建遮罩 ->
int x=(~0); //All Ones 11111111111111111111111111111111
int left=(1<<i)-1; // 11
int right=x-((1<<j)-1); // 11111111111111111111111111000000
int mask=left | right; // 11111111111111111111111111000011
第 2 步：清除给定数字中 i 和 j 之间的位 'n' ->
int cleared = n & mask; // 10000000000000000000000000000000
第 3 步：将 m 放入 n 中 i 和 j 之间（清除位）->
int ans= cleared | m<<i; 10000000000000000000000001010100