找到最接近的具有相同权重 O(1) 的整数
Find the closest integer with same weight O(1)
我正在解决这个问题：
整数的二进制表示中1的个数称为该数的权重。以下算法找到具有相同权重的最接近的整数。例如，对于 123 (0111 1011)2，最接近的整数是 125 (0111 1101)2。
O(n) 的解决方案
其中 n 是输入数字的宽度，是通过交换第一对不同的连续位的位置来实现的。
有人可以给我一些在 O(1) 运行时和 space 中解决它的提示吗？
谢谢
正如 ajayv 已经评论的那样，这在 O(1) 中无法真正完成，因为答案总是取决于输入的位数。然而，如果我们将 O(1) 解释为意味着我们有一些原始整数数据作为输入，并且我们对该整数执行的所有逻辑和算术运算都是 O(1)（没有位循环），那么问题可以在常数时间内解决。当然，如果我们从 32 位整数更改为 64 位整数，运行 时间会增加，因为算术运算在硬件上需要更长的时间。
一种可能的解决方案是使用以下函数。第一个给你一个数字，其中只有 x 的最低设置位被设置
int lowestBitSet(int x){
( x & ~(x-1) )
}
第二个最低位未设置
int lowestBitNotSet(int x){
return ~x & (x+1);
}
如果你在纸上做几个这样的例子，你就会明白它们是如何工作的。
现在您可以使用这两个函数找到您需要更改的位，然后使用您已经描述的算法。
C++ 实现（不检查没有答案的情况）
unsigned int closestInt(unsigned int x){
unsigned int ns=lowestBitNotSet(x);
unsigned int s=lowestBitSet(x);
if (ns>s){
x|=ns;
x^=ns>>1;
}
else{
x^=s;
x|=s>>1;
}
return x;
}
static void findClosestIntWithSameWeight(uint x)
{
uint xWithfirstBitSettoZero = x & (x - 1);
uint xWithOnlyfirstbitSet = x & ~(x - 1);
uint xWithNextTofirstBitSet = xWithOnlyfirstbitSet >> 1;
uint closestWeightNum = xWithfirstBitSettoZero | xWithNextTofirstBitSet;
Console.WriteLine("Closet Weight for {0} is {1}", x, closestWeightNum);
}
Java 解法：
//Swap the two rightmost consecutive bits that are different
for (int i = 0; i < 64; i++) {
if ((((x >> i) & 1) ^ ((x >> (i+1)) & 1)) == 1) {
// then swap them or flip their bits
int mask = (1 << i) | (1 << i + 1);
x = x ^ mask;
System.out.println("x = " + x);
return;
}
}
这个问题可以看作是“在数字的位表示中交换哪些不同的位，以便结果数字最接近原始数字？”
因此，如果我们要交换索引 k1 和 k2 处的位与 k2 > k1，数字之间的差异将是 2^k2 - 2^k1。我们的目标是最小化这种差异。假设位表示不是全 0 或全 1，一个简单的观察结果表明，如果我们将 |k2 - k1| 保持为最小值，则差异将最小。最小值可以是 1。因此，如果我们能够找到两个连续的不同位，从最低有效位（索引 = 0）开始，我们的工作就完成了。
从Least Significant Bit开始到最右边set bit全部为1的情况
k2
|
7 6 5 4 3 2 1 0
---------------
n: 1 1 1 0 1 0 1 1
rightmostSetBit: 0 0 0 0 0 0 0 1
rightmostNotSetBit: 0 0 0 0 0 1 0 0 rightmostNotSetBit > rightmostSetBit so,
difference: 0 0 0 0 0 0 1 0 i.e. rightmostNotSetBit - (rightmostNotSetBit >> 1):
---------------
n + difference: 1 1 1 0 1 1 0 1
从Least Significant Bit开始到最右边set bit全部为0的情况
k2
|
7 6 5 4 3 2 1 0
---------------
n: 1 1 1 0 1 1 0 0
rightmostSetBit: 0 0 0 0 0 1 0 0
rightmostNotSetBit: 0 0 0 0 0 0 0 1 rightmostSetBit > rightmostNotSetBit so,
difference: 0 0 0 0 0 0 1 0 i.e. rightmostSetBit -(rightmostSetBit>> 1)
---------------
n - difference: 1 1 1 0 1 0 1 0
边缘情况，当然是全 0 或全 1 的情况。
public static long closestToWeight(long n){
if(n <= 0 /* If all 0s */ || (n+1) == Integer.MIN_VALUE /* n is MAX_INT */)
return -1;
long neg = ~n;
long rightmostSetBit = n&~(n-1);
long rightmostNotSetBit = neg&~(neg-1);
if(rightmostNotSetBit > rightmostSetBit){
return (n + (rightmostNotSetBit - (rightmostNotSetBit >> 1)));
}
return (n - (rightmostSetBit - (rightmostSetBit >> 1)));
}
python中的代码：
def closest_int_same_bit_count(x):
if (x & 1) != ((x >> 1) & 1):
return x ^ 0x3
diff = x ^ (x >> 1)
rbs = diff & ~(diff - 1)
i = int(math.log(rbs, 2))
return x ^ (1 << i | 1 << i + 1)
要在O(1)时间复杂度内解决这个问题可以认为有两个主要情况：
1) When LSB is '0':
在这种情况下，第一个“1”必须向右移动一个位置。
Input : "10001000"
Out ::: "10000100"
2) When LSB is '1':
在这种情况下，第一个“0”必须设置为“1”，第一个“1”必须设置为“0”。
Input : "10000111"
Out ::: "10001110"
Java 中的下一个方法代表一个解决方案。
private static void findClosestInteger(String word) { // ex: word = "10001000"
System.out.println(word); // Print initial binary format of the number
int x = Integer.parseInt(word, 2); // Convert String to int
if((x & 1) == 0) { // Evaluates LSB value
// Case when LSB = '0':
// Input: x = 10001000
int firstOne = x & ~(x -1); // get first '1' position (from right to left)
// firstOne = 00001000
x = x & (x - 1); // set first '1' to '0'
// x = 10000000
x = x | (firstOne >> 1); // "shift" first '1' with one position to right
// x = 10000100
} else {
// Case when LSB = '1':
// Input: x = 10000111
int firstZero = ~x & ~(~x - 1); // get first '0' position (from right to left)
// firstZero = 00001000
x = x & (~1); // set first '1', which is the LSB, to '0'
// x = 10000110
x = x | firstZero; // set first '0' to '1'
// x = 10001110
}
for(int i = word.length() - 1; i > -1 ; i--) { // print the closest integer with same weight
System.out.print("" + ( ( (x & 1 << i) != 0) ? 1 : 0) );
}
}
在 EPI 的问题 4.4 中可以找到对这个问题的很好的解释。
（编程面试要素）
如果您没有这本书，另一个地方是 geeksforgeeks.org 上的这个 link。
（这个时间复杂度可能有误link）
这里有两件事你应该记住（提示如果你想自己解决这个问题）：
您可以使用 x & (x - 1) 清除最低设置位（不要与 LSB - 最低有效位混淆）
可以用x & ~(x - 1)到get/extract设置最低位
如果您知道 O(n) 解决方案，您就会知道我们需要找到与 LSB 不同的第一位的索引。
如果您不知道 LBS 是什么：
0000 0000
^ // it's bit all the way to the right of a binary string.
取二进制数1011 1000（十进制为184）
与 LSB 不同的第一位：
1011 1000
^ // this one
我们将其记录为 K1 = 0000 1000
然后我们需要将它与右边的下一位交换：
0000 1000
^ // this one
我们将其记录为 K2 = 0000 0100
按位或 K1 和 K2 在一起，你会得到一个掩码
mask = K1 | k2 // 0000 1000 | 0000 0100 -> 0000 1100
将掩码与原始数字按位异或，您将得到正确的 output/swap
number ^ mask // 1011 1000 ^ 0000 1100 -> 1011 0100
现在，在我们将所有内容放在一起之前，我们必须考虑这样一个事实，即 LSB 可能是 0001，之后的一堆位也可能是 1000 1111。所以我们必须处理第一位不同于LSB的两种情况；它可能是 1 或 0。
首先我们有一个条件来测试 LSB 是 1 还是 0：x & 1
IF 1 return x XORed with the return of a helper function
这个辅助函数有第二个参数，它的值取决于条件是否为真。 func(x, 0xFFFFFFFF) // if true // 0xFFFFFFFF 64 bit word with all bits set to 1
否则我们将跳过 if 语句和 return 类似的表达式，但为第二个参数提供不同的值。
return x XORed with func(x, 0x00000000) // 64 bit word with all bits set to 0. You could alternatively just pass 0 but I did this for consistency
我们的辅助函数 return 是一个掩码，我们将用它与原始数字进行异或以获得我们的输出。
它有两个参数，我们的原始数字和一个掩码，在这个表达式中使用：
(x ^ mask) & ~((x ^ mask) - 1)
这给了我们一个新数字，索引 K1 处的位始终设置为 1。
然后它将该位 1 向右移动（即索引 K2），然后将其与自身进行或运算以创建我们最终的掩码
0000 1000 >> 1 -> 0000 0100 | 0001 0000 -> 0000 1100
这一切都是用 C++ 实现的，如下所示：
unsigned long long int closestIntSameBitCount(unsigned long long int n)
{
if (n & 1)
return n ^= getSwapMask(n, 0xFFFFFFFF);
return n ^= getSwapMask(n, 0x00000000);
}
// Helper function
unsigned long long int getSwapMask(unsigned long long int n, unsigned long long int mask)
{
unsigned long long int swapBitMask = (n ^ mask) & ~((n ^ mask) - 1);
return swapBitMask | (swapBitMask >> 1);
}
记下表达式(x ^ mask) & ~((x ^ mask) - 1)
我现在 运行 通过我的示例 1011 1000:
// start of closestIntSameBitCount
if (0) // 1011 1000 & 1 -> 0000 0000
// start of getSwapMask
getSwapMask(1011 1000, 0x00000000)
swapBitMask = (x ^ mask) & ~1011 0111 // ((x ^ mask) - 1) = 1011 1000 ^ .... 0000 0000 -> 1011 1000 - 1 -> 1011 0111
swapBitMask = (x ^ mask) & 0100 1000 // ~1011 0111 -> 0100 1000
swapBitMask = 1011 1000 & 0100 1000 // (x ^ mask) = 1011 1000 ^ .... 0000 0000 -> 1011 1000
swapBitMask = 0000 1000 // 1011 1000 & 0100 1000 -> 0000 1000
return swapBitMask | 0000 0100 // (swapBitMask >> 1) = 0000 1000 >> 1 -> 0000 0100
return 0000 1100 // 0000 1000 | 0000 0100 -> 0000 11000
// end of getSwapMask
return 1011 0100 // 1011 1000 ^ 0000 11000 -> 1011 0100
// end of closestIntSameBitCount
这里有一个完整的 运行ning 例子，如果你想自己编译 运行：
#include <iostream>
#include <stdio.h>
#include <bitset>
unsigned long long int closestIntSameBitCount(unsigned long long int n);
unsigned long long int getSwapMask(unsigned long long int n, unsigned long long int mask);
int main()
{
unsigned long long int number;
printf("Pick a number: ");
std::cin >> number;
std::bitset<64> a(number);
std::bitset<64> b(closestIntSameBitCount(number));
std::cout << a
<< "\n"
<< b
<< std::endl;
}
unsigned long long int closestIntSameBitCount(unsigned long long int n)
{
if (n & 1)
return n ^= getSwapMask(n, 0xFFFFFFFF);
return n ^= getSwapMask(n, 0x00000000);
}
// Helper function
unsigned long long int getSwapMask(unsigned long long int n, unsigned long long int mask)
{
unsigned long long int swapBitMask = (n ^ mask) & ~((n ^ mask) - 1);
return swapBitMask | (swapBitMask >> 1);
}
尝试了 Python 中的问题。可以被视为 的翻译，并处理了边缘情况：
def closest_int_same_bit_count(x):
# if all bits of x are 0 or 1, there can't be an answer
if x & sys.maxsize in {sys.maxsize, 0}:
raise ValueError("All bits are 0 or 1")
rightmost_set_bit = x & ~(x - 1)
next_un_set_bit = ~x & (x + 1)
if next_un_set_bit > rightmost_set_bit:
# 0 shifted to the right e.g 0111 -> 1011
x ^= next_un_set_bit | next_un_set_bit >> 1
else:
# 1 shifted to the right 1000 -> 0100
x ^= rightmost_set_bit | rightmost_set_bit >> 1
return x
同样jigsawmnc的提供如下：
def closest_int_same_bit_count(x):
# if all bits of x are 0 or 1, there can't be an answer
if x & sys.maxsize in {sys.maxsize, 0}:
raise ValueError("All bits are 0 or 1")
rightmost_set_bit = x & ~(x - 1)
next_un_set_bit = ~x & (x + 1)
if next_un_set_bit > rightmost_set_bit:
# 0 shifted to the right e.g 0111 -> 1011
x += next_un_set_bit - (next_un_set_bit >> 1)
else:
# 1 shifted to the right 1000 -> 0100
x -= rightmost_set_bit - (rightmost_set_bit >> 1)
return x
这是我解决问题的方法。我想@jigsawmnc 很好地解释了为什么我们需要 |k2 -k1|到最低限度。因此，为了找到最接近的具有相同权重的整数，我们需要找到翻转连续位的位置，然后再次翻转它们以获得答案。为此，我们可以移动 1 号单元。取同数异或。这将在所有存在翻转的位置设置位。找到 XOR 的最低有效位。这将为您提供最小的翻转位置。为位置和下一位创建掩码。采用异或运算，这应该就是答案。如果数字全为 0 或全为 1，这将不起作用
这是它的代码。
def variant_closest_int(x: int) -> int:
if x == 0 or ~x == 0:
raise ValueError('All bits are 0 or 1')
x_ = x >> 1
lsb = x ^ x_
mask_ = lsb & ~(lsb - 1)
mask = mask_ | (mask_ << 1)
return x ^ mask
我的解决方案利用了整数的奇偶校验。我认为我得到 LSB masks 的方式可以简化
def next_weighted_int(x):
if x % 2 == 0:
lsb_mask = ( ((x - 1) ^ x) >> 1 ) + 1 # Gets a mask for the first 1
x ^= lsb_mask
x |= (lsb_mask >> 1)
return x
lsb_mask = ((x ^ (x + 1)) >> 1 ) + 1 # Gets a mask for the first 0
x |= lsb_mask
x ^= (lsb_mask >> 1)
return x
只是分享我对这个问题的 python 解决方案：
def same closest_int_same_bit_count(a):
x = a + (a & 1) # change last bit to 0
bit = (x & ~(x-1)) # get last set bit
return a ^ (bit | bit >> 1) # swap set bit with unset bit
func findClosestIntegerWithTheSameWeight2(x int) int {
rightMost0 := ^x & (x + 1)
rightMost1 := x & (-x)
if rightMost0 > 1 {
return (x ^ rightMost0) ^ (rightMost0 >> 1)
} else {
return (x ^ rightMost1) ^ (rightMost1 >> 1)
}
}
我正在解决这个问题：
整数的二进制表示中1的个数称为该数的权重。以下算法找到具有相同权重的最接近的整数。例如，对于 123 (0111 1011)2，最接近的整数是 125 (0111 1101)2。
O(n) 的解决方案 其中 n 是输入数字的宽度，是通过交换第一对不同的连续位的位置来实现的。
有人可以给我一些在 O(1) 运行时和 space 中解决它的提示吗？
谢谢
正如 ajayv 已经评论的那样，这在 O(1) 中无法真正完成，因为答案总是取决于输入的位数。然而，如果我们将 O(1) 解释为意味着我们有一些原始整数数据作为输入，并且我们对该整数执行的所有逻辑和算术运算都是 O(1)（没有位循环），那么问题可以在常数时间内解决。当然，如果我们从 32 位整数更改为 64 位整数，运行 时间会增加，因为算术运算在硬件上需要更长的时间。
一种可能的解决方案是使用以下函数。第一个给你一个数字，其中只有 x 的最低设置位被设置
int lowestBitSet(int x){
( x & ~(x-1) )
}
第二个最低位未设置
int lowestBitNotSet(int x){
return ~x & (x+1);
}
如果你在纸上做几个这样的例子，你就会明白它们是如何工作的。
现在您可以使用这两个函数找到您需要更改的位，然后使用您已经描述的算法。
C++ 实现（不检查没有答案的情况）
unsigned int closestInt(unsigned int x){
unsigned int ns=lowestBitNotSet(x);
unsigned int s=lowestBitSet(x);
if (ns>s){
x|=ns;
x^=ns>>1;
}
else{
x^=s;
x|=s>>1;
}
return x;
}
static void findClosestIntWithSameWeight(uint x)
{
uint xWithfirstBitSettoZero = x & (x - 1);
uint xWithOnlyfirstbitSet = x & ~(x - 1);
uint xWithNextTofirstBitSet = xWithOnlyfirstbitSet >> 1;
uint closestWeightNum = xWithfirstBitSettoZero | xWithNextTofirstBitSet;
Console.WriteLine("Closet Weight for {0} is {1}", x, closestWeightNum);
}
Java 解法：
//Swap the two rightmost consecutive bits that are different
for (int i = 0; i < 64; i++) {
if ((((x >> i) & 1) ^ ((x >> (i+1)) & 1)) == 1) {
// then swap them or flip their bits
int mask = (1 << i) | (1 << i + 1);
x = x ^ mask;
System.out.println("x = " + x);
return;
}
}
这个问题可以看作是“在数字的位表示中交换哪些不同的位，以便结果数字最接近原始数字？”
因此，如果我们要交换索引 k1 和 k2 处的位与 k2 > k1，数字之间的差异将是 2^k2 - 2^k1。我们的目标是最小化这种差异。假设位表示不是全 0 或全 1，一个简单的观察结果表明，如果我们将 |k2 - k1| 保持为最小值，则差异将最小。最小值可以是 1。因此，如果我们能够找到两个连续的不同位，从最低有效位（索引 = 0）开始，我们的工作就完成了。
从Least Significant Bit开始到最右边set bit全部为1的情况
k2
|
7 6 5 4 3 2 1 0
---------------
n: 1 1 1 0 1 0 1 1
rightmostSetBit: 0 0 0 0 0 0 0 1
rightmostNotSetBit: 0 0 0 0 0 1 0 0 rightmostNotSetBit > rightmostSetBit so,
difference: 0 0 0 0 0 0 1 0 i.e. rightmostNotSetBit - (rightmostNotSetBit >> 1):
---------------
n + difference: 1 1 1 0 1 1 0 1
从Least Significant Bit开始到最右边set bit全部为0的情况
k2
|
7 6 5 4 3 2 1 0
---------------
n: 1 1 1 0 1 1 0 0
rightmostSetBit: 0 0 0 0 0 1 0 0
rightmostNotSetBit: 0 0 0 0 0 0 0 1 rightmostSetBit > rightmostNotSetBit so,
difference: 0 0 0 0 0 0 1 0 i.e. rightmostSetBit -(rightmostSetBit>> 1)
---------------
n - difference: 1 1 1 0 1 0 1 0
边缘情况，当然是全 0 或全 1 的情况。
public static long closestToWeight(long n){
if(n <= 0 /* If all 0s */ || (n+1) == Integer.MIN_VALUE /* n is MAX_INT */)
return -1;
long neg = ~n;
long rightmostSetBit = n&~(n-1);
long rightmostNotSetBit = neg&~(neg-1);
if(rightmostNotSetBit > rightmostSetBit){
return (n + (rightmostNotSetBit - (rightmostNotSetBit >> 1)));
}
return (n - (rightmostSetBit - (rightmostSetBit >> 1)));
}
python中的代码：
def closest_int_same_bit_count(x):
if (x & 1) != ((x >> 1) & 1):
return x ^ 0x3
diff = x ^ (x >> 1)
rbs = diff & ~(diff - 1)
i = int(math.log(rbs, 2))
return x ^ (1 << i | 1 << i + 1)
要在O(1)时间复杂度内解决这个问题可以认为有两个主要情况：
1) When LSB is '0':
在这种情况下，第一个“1”必须向右移动一个位置。
Input : "10001000"
Out ::: "10000100"
2) When LSB is '1':
在这种情况下，第一个“0”必须设置为“1”，第一个“1”必须设置为“0”。
Input : "10000111"
Out ::: "10001110"
Java 中的下一个方法代表一个解决方案。
private static void findClosestInteger(String word) { // ex: word = "10001000"
System.out.println(word); // Print initial binary format of the number
int x = Integer.parseInt(word, 2); // Convert String to int
if((x & 1) == 0) { // Evaluates LSB value
// Case when LSB = '0':
// Input: x = 10001000
int firstOne = x & ~(x -1); // get first '1' position (from right to left)
// firstOne = 00001000
x = x & (x - 1); // set first '1' to '0'
// x = 10000000
x = x | (firstOne >> 1); // "shift" first '1' with one position to right
// x = 10000100
} else {
// Case when LSB = '1':
// Input: x = 10000111
int firstZero = ~x & ~(~x - 1); // get first '0' position (from right to left)
// firstZero = 00001000
x = x & (~1); // set first '1', which is the LSB, to '0'
// x = 10000110
x = x | firstZero; // set first '0' to '1'
// x = 10001110
}
for(int i = word.length() - 1; i > -1 ; i--) { // print the closest integer with same weight
System.out.print("" + ( ( (x & 1 << i) != 0) ? 1 : 0) );
}
}
在 EPI 的问题 4.4 中可以找到对这个问题的很好的解释。
（编程面试要素）
如果您没有这本书，另一个地方是 geeksforgeeks.org 上的这个 link。
（这个时间复杂度可能有误link）
这里有两件事你应该记住（提示如果你想自己解决这个问题）：
您可以使用 x & (x - 1) 清除最低设置位（不要与 LSB - 最低有效位混淆）
可以用x & ~(x - 1)到get/extract设置最低位
如果您知道 O(n) 解决方案，您就会知道我们需要找到与 LSB 不同的第一位的索引。
如果您不知道 LBS 是什么：
0000 0000
^ // it's bit all the way to the right of a binary string.
取二进制数1011 1000（十进制为184）
与 LSB 不同的第一位：
1011 1000
^ // this one
我们将其记录为 K1 = 0000 1000
然后我们需要将它与右边的下一位交换：
0000 1000
^ // this one
我们将其记录为 K2 = 0000 0100
按位或 K1 和 K2 在一起，你会得到一个掩码
mask = K1 | k2 // 0000 1000 | 0000 0100 -> 0000 1100
将掩码与原始数字按位异或，您将得到正确的 output/swap
number ^ mask // 1011 1000 ^ 0000 1100 -> 1011 0100
现在，在我们将所有内容放在一起之前，我们必须考虑这样一个事实，即 LSB 可能是 0001，之后的一堆位也可能是 1000 1111。所以我们必须处理第一位不同于LSB的两种情况；它可能是 1 或 0。
首先我们有一个条件来测试 LSB 是 1 还是 0：x & 1
IF 1 return x XORed with the return of a helper function
这个辅助函数有第二个参数，它的值取决于条件是否为真。 func(x, 0xFFFFFFFF) // if true // 0xFFFFFFFF 64 bit word with all bits set to 1
否则我们将跳过 if 语句和 return 类似的表达式，但为第二个参数提供不同的值。
return x XORed with func(x, 0x00000000) // 64 bit word with all bits set to 0. You could alternatively just pass 0 but I did this for consistency
我们的辅助函数 return 是一个掩码，我们将用它与原始数字进行异或以获得我们的输出。
它有两个参数，我们的原始数字和一个掩码，在这个表达式中使用：
(x ^ mask) & ~((x ^ mask) - 1)
这给了我们一个新数字，索引 K1 处的位始终设置为 1。
然后它将该位 1 向右移动（即索引 K2），然后将其与自身进行或运算以创建我们最终的掩码
0000 1000 >> 1 -> 0000 0100 | 0001 0000 -> 0000 1100
这一切都是用 C++ 实现的，如下所示：
unsigned long long int closestIntSameBitCount(unsigned long long int n)
{
if (n & 1)
return n ^= getSwapMask(n, 0xFFFFFFFF);
return n ^= getSwapMask(n, 0x00000000);
}
// Helper function
unsigned long long int getSwapMask(unsigned long long int n, unsigned long long int mask)
{
unsigned long long int swapBitMask = (n ^ mask) & ~((n ^ mask) - 1);
return swapBitMask | (swapBitMask >> 1);
}
记下表达式(x ^ mask) & ~((x ^ mask) - 1)
我现在 运行 通过我的示例 1011 1000:
// start of closestIntSameBitCount
if (0) // 1011 1000 & 1 -> 0000 0000
// start of getSwapMask
getSwapMask(1011 1000, 0x00000000)
swapBitMask = (x ^ mask) & ~1011 0111 // ((x ^ mask) - 1) = 1011 1000 ^ .... 0000 0000 -> 1011 1000 - 1 -> 1011 0111
swapBitMask = (x ^ mask) & 0100 1000 // ~1011 0111 -> 0100 1000
swapBitMask = 1011 1000 & 0100 1000 // (x ^ mask) = 1011 1000 ^ .... 0000 0000 -> 1011 1000
swapBitMask = 0000 1000 // 1011 1000 & 0100 1000 -> 0000 1000
return swapBitMask | 0000 0100 // (swapBitMask >> 1) = 0000 1000 >> 1 -> 0000 0100
return 0000 1100 // 0000 1000 | 0000 0100 -> 0000 11000
// end of getSwapMask
return 1011 0100 // 1011 1000 ^ 0000 11000 -> 1011 0100
// end of closestIntSameBitCount
这里有一个完整的 运行ning 例子，如果你想自己编译 运行：
#include <iostream>
#include <stdio.h>
#include <bitset>
unsigned long long int closestIntSameBitCount(unsigned long long int n);
unsigned long long int getSwapMask(unsigned long long int n, unsigned long long int mask);
int main()
{
unsigned long long int number;
printf("Pick a number: ");
std::cin >> number;
std::bitset<64> a(number);
std::bitset<64> b(closestIntSameBitCount(number));
std::cout << a
<< "\n"
<< b
<< std::endl;
}
unsigned long long int closestIntSameBitCount(unsigned long long int n)
{
if (n & 1)
return n ^= getSwapMask(n, 0xFFFFFFFF);
return n ^= getSwapMask(n, 0x00000000);
}
// Helper function
unsigned long long int getSwapMask(unsigned long long int n, unsigned long long int mask)
{
unsigned long long int swapBitMask = (n ^ mask) & ~((n ^ mask) - 1);
return swapBitMask | (swapBitMask >> 1);
}
尝试了 Python 中的问题。可以被视为
def closest_int_same_bit_count(x):
# if all bits of x are 0 or 1, there can't be an answer
if x & sys.maxsize in {sys.maxsize, 0}:
raise ValueError("All bits are 0 or 1")
rightmost_set_bit = x & ~(x - 1)
next_un_set_bit = ~x & (x + 1)
if next_un_set_bit > rightmost_set_bit:
# 0 shifted to the right e.g 0111 -> 1011
x ^= next_un_set_bit | next_un_set_bit >> 1
else:
# 1 shifted to the right 1000 -> 0100
x ^= rightmost_set_bit | rightmost_set_bit >> 1
return x
同样jigsawmnc的
def closest_int_same_bit_count(x):
# if all bits of x are 0 or 1, there can't be an answer
if x & sys.maxsize in {sys.maxsize, 0}:
raise ValueError("All bits are 0 or 1")
rightmost_set_bit = x & ~(x - 1)
next_un_set_bit = ~x & (x + 1)
if next_un_set_bit > rightmost_set_bit:
# 0 shifted to the right e.g 0111 -> 1011
x += next_un_set_bit - (next_un_set_bit >> 1)
else:
# 1 shifted to the right 1000 -> 0100
x -= rightmost_set_bit - (rightmost_set_bit >> 1)
return x
这是我解决问题的方法。我想@jigsawmnc 很好地解释了为什么我们需要 |k2 -k1|到最低限度。因此，为了找到最接近的具有相同权重的整数，我们需要找到翻转连续位的位置，然后再次翻转它们以获得答案。为此，我们可以移动 1 号单元。取同数异或。这将在所有存在翻转的位置设置位。找到 XOR 的最低有效位。这将为您提供最小的翻转位置。为位置和下一位创建掩码。采用异或运算，这应该就是答案。如果数字全为 0 或全为 1，这将不起作用 这是它的代码。
def variant_closest_int(x: int) -> int:
if x == 0 or ~x == 0:
raise ValueError('All bits are 0 or 1')
x_ = x >> 1
lsb = x ^ x_
mask_ = lsb & ~(lsb - 1)
mask = mask_ | (mask_ << 1)
return x ^ mask
我的解决方案利用了整数的奇偶校验。我认为我得到 LSB masks 的方式可以简化
def next_weighted_int(x):
if x % 2 == 0:
lsb_mask = ( ((x - 1) ^ x) >> 1 ) + 1 # Gets a mask for the first 1
x ^= lsb_mask
x |= (lsb_mask >> 1)
return x
lsb_mask = ((x ^ (x + 1)) >> 1 ) + 1 # Gets a mask for the first 0
x |= lsb_mask
x ^= (lsb_mask >> 1)
return x
只是分享我对这个问题的 python 解决方案：
def same closest_int_same_bit_count(a):
x = a + (a & 1) # change last bit to 0
bit = (x & ~(x-1)) # get last set bit
return a ^ (bit | bit >> 1) # swap set bit with unset bit
func findClosestIntegerWithTheSameWeight2(x int) int {
rightMost0 := ^x & (x + 1)
rightMost1 := x & (-x)
if rightMost0 > 1 {
return (x ^ rightMost0) ^ (rightMost0 >> 1)
} else {
return (x ^ rightMost1) ^ (rightMost1 >> 1)
}
}