使用位操作处理负数

Question

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

我试图借助位操作来解决这个挑战，并得到了一个工作解决方案，它适用于非负整数（请参阅下面的代码和测试输出）。对于负数，它 return 是否定答案的绝对值。

我在这里错过了什么？

我当前的代码如下：

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。原因可能是编译运行你代码的judge是64位机器(know more here).

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

    return int(int32(result))

或者您可以改为将 result 声明为 int32 并将其类型转换为 int 而 returning

    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 个零）作为值来遍历每个点

使用位操作处理负数

Handling negative numbers with bit manipulation

algorithm

bit-manipulation

go