0

我试图利用一个布尔向量将存储压缩到一个位的事实。以下配方应该是确定 int 数组是否包含重复的好方法（或者是吗？我的整个想法是否存在固有缺陷？）。我不明白为什么我的编译器 XCode 不喜欢

INT_MAX - INT_MIN + 1

下面的代码行。我尝试将表达式转换为 long，但我得到了同样的警告。任何帮助是极大的赞赏！

bool contains_repeats_3(const std::vector<int>& V) { 
    std::vector<bool> bv (INT_MAX - INT_MIN + 1, 0); // <------ That's the problem line
    for (std::vector<int>::const_iterator it = V.begin() ; it != V.end(); ++it) {
        if (bv[*it - INT_MIN] == 1) {
            return true;
        } else { 
            bv[*it - INT_MIN] == 1;
        }
    }
   return false;    
}
4

2 回答 2

3

首先，您必须强制转换的不是表达式，而是单个操作数，如(long) INT_MAX - (long) INT_MIN + 1. 只铸造第一个就足够了。

其次，范围很可能与您平台上long的范围相同int，这意味着强制转换long不会防止溢出。long long假设您可以使用它，您可能必须强制转换为 。

第三，你确定你需要那个大小的向量吗？我希望std::vector<bool>在您的平台上实现为位向量。或者至少您的平台是 64 位的。在 32 位平台上，您正在突破数组大小的限制。请注意，std::vector不保证您有这种容量。您可能希望bv.max_size()您的向量能够查看它是否能够容纳那么多元素。

于 2013-11-08T06:46:51.193 回答
2

从根本上讲，您的问题是 INT_MAX 为正而 INT_MIN 为负，因此当您从 MAX 中减去 MIN 时，您实际上是在添加。

10 - -2 = 10 + 2 = 12

然后考虑，您要添加的数字已经是 int 可以存储的最大数字，而您要添加的数字是最大可能的负值。INT_MAX 和 0 的差是 INT_MAX，所以 INT_MAX 和任何<0 的差大于 INT_MAX。

(INT_MAX + 1) > INT_MAX
(INT_MAX - -1) > INT_MAX

基本上 INT_MAX + any>0 需要比 int 更多的位来描述。这是溢出，说“进位”的编程方式（它只有一位来注释进位，所以它可能不止一个）

想象一下，您有 2 位来描述一个有符号数，四种可能的位组合：b00 (0)、b01 (+1)、b10 (-2)、b11 (-1)。

我们将 -1 分配给 b11，因为 b11 - b01 = b10 和 b00 - b01 = b11+sign

结果：

TINYINT_MAX = 1  (b01)
TINYINT_MIN = -2 (b10)

以下是您的公式的计算方式：

(TINYINT_MAX - TINYINT_MIN +  1 )
 b01           b10           b01
( 1 - -2  +  1 )
 b01  b10   b01

( 1  +  2  +  1 ) <-- things go pear shaped here.
 b01   xxx   b01

( 3  +  1 )
 xxx   b01

= 4

如果我们去无符号，我们可以处理“3”，但是 4 (b100) 需要比我们更多的位。

但是我们的数字系统只支持+1、0、-1、-2，所以当我们说“-TINYINT_MIN”时我们被打破了。

于 2013-11-08T07:15:01.650 回答