使用位操作处理负数

Question

我正试图解决这个leetcode挑战Majority Element。给出了一个整数nums的数组，它总是包含至少个len(nums)/2+1元素，其余元素是随机的。任务是返回多数元素。

我试图在比特操作的帮助下解决这个挑战，并得到了一个有效的解决方案，它适用于非负整数(请参阅下面的代码和测试输出(。对于负数，它返回否定答案的绝对值。

我在这里错过了什么？

我当前的代码如下：

func majorityElement(nums []int) int {
var bits [32]int // hash of bits
// for every number
for _, num := range nums {
// reading whether a bit is one for each register
for i := 0; i < 32; i++ {
// if yes, incrementing the counter in hash
if num&(1<<i) > 0 {
bits[i] += 1
}
}
}

result := 0
// restoring the majority number bit by bit back
for i := range bits {
// if the majority of ones => it's a 1, else 0 and do nothing
if bits[i] > len(nums)/2 { // 1
result |= 1 << i
}
}
return result
}

它产生以下结果：

true: want 3, got 3 for [3 2 3]
true: want 4, got 4 for [4 5 4]
true: want 2, got 2 for [2 2 1 1 1 2 2]
true: want 4, got 4 for [4 5 4]
false: want -2147483648, got 2147483648 for [-2147483648]

Answer 1

代码的问题是result自动被视为int64。原因可能是编译和运行代码的判断程序是一台64位机器(在这里了解更多信息(。

为了避免这种情况，我们可以首先将结果转换为int32，然后将其强制转换回int作为所需的返回类型

return int(int32(result))

或者您可以将result声明为int32，并在返回时将其类型转换为int

var result int32
// .....
return int(result)

进一步解释：

• 为了简单起见，让我们考虑int8数据类型
• 所有可能的值都有8位
• 最大正值为127(二进制表示：01111111(
• 现在尝试在127上加1，它变成-128！(二进制表示：10000000(
• 为什么？为了表示带符号数据类型中的负值，我们总是将最左边(也称为最高有效位(的位设置为1

10000001 represents -128 + 1 = -127
10000010 represents -128 + 2 = -126
10000011 represents -128 + 3 = -125
...
11111110 represents -128 + 126 = -2
11111111 represents -128 + 127 = -1

• 这里的主要收获是所有负整数都有最左边的，即最高有效位设置为1
• 现在，当你表示128，即int16中的二进制数字10000000时，它变成0000000010000000
• 在16位整数中，128的最高有效位没有设置为1，因此它不是负数
• 您可以尝试使用int32作为数据类型，2147483648(二进制表示：1后跟31个零(作为值来遍历每个点