algorithm - 通过位操作处理负数

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位计算机(know more here)。
为了避免这种情况，我们可以先将结果转换为int32，然后将其转换为int作为所需的返回类型

    return int(int32(result))

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

    var result int32

    // .....

    return int(result)

进一步说明:

为简单起见，让我们考虑int8数据类型

所有可能的值都有8位

最大正值为127(二进制表示:01111111)

现在尝试将1加到127，它变成-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，因此它不是负数

您可以尝试使用int32作为数据类型并使用2147483648(二进制表示形式:1，后跟31个零)作为值

遍历每个点。