0

如果我使用单个 int 来表示 ascii 字符集，如何使用它来减少 8 倍的存储空间？与 256 个布尔值的数组相比？单个 int 也像位向量一样工作。

java中的布尔值将占用1位，因为它只能表示真或假值。例如，如果我有一个布尔值数组。boolean[] char_set = new boolean[256] 这将占用 256 位对吗？我正在阅读，如果我使用像位向量这样的单个 int，这意味着我可以使用 32 位来覆盖 256 个值。我想这是减少了 8 倍。但是为什么下面的代码有效？

它正在检查字符串中是否有任何重复项。他们假设一个 ascii 字符集。Str 是一些字符串。

int checker = 0;
for(int i=0;i<str.length();i++)
{
  int val = str.charAt(i) - 'a';
  if(checker& (1<<val)) > 0)
  {
     return false;
  }
  checker |= (1<<val);
}
  return true;
}

有人可以特别解释一下在这种情况下位向量逻辑是如何工作的。他们假设字符串包含小写字符。

4

3 回答 3

2

Anint是 32 位，而不是 256 位。仅代表一组 256 个可能的项目是不够的。你需要8个。我不确定你的意思是你只能使用 32 位。

目前还不清楚你在循环什么——什么是str？从 0 到 255 的所有 256 个值？我很怀疑，因为你在减去'a'。您的值域是否只有 32 个可能的字符？然后确定你可以使用32位。但是 256 是从哪里来的呢？

您的掩码条件需要!= 0适用于最高位集。

（Aboolean的“真实”大小对 Java 程序员来说是不透明的。实际上，您会发现它不是 1 位（机器不是可位寻址的），甚至不是 1 字节。Java 实际上使用了整个 32 位词。但这与您的问题并没有真正的关系。）

于 2012-09-15T19:14:07.090 回答
1

这段代码所做的只是“标记”一点以表示字符的存在。
在你的情况下：int val = str.charAt(i) - 'a';。如果当前字符等于，a则此行检查是否设置了零位（LSB）。如果是那么之前已经看到过。否则它会设置它。如果当前字符是，则将等于，因此设置下一个更高位（第一位），依此类推。 基本上在 ascii 字符集上，只使用一个这种方式就可以节省空间，因为它与数组相反，但是这个代码只能处理字母，同时处理所有的 ASCII，代码会更清晰val0checker& (1<<val)abval1
intboolean[256]a-zboolean[256]

于 2012-09-15T19:20:19.937 回答
0

java中的布尔值将占用1位，因为它只能表示真或假值。例如，如果我有一个布尔值数组。boolean[] char_set = new boolean[256] 这将占用 256 位对吗？

这是不正确的。现代计算机无法寻址单个位。

此外，要表示 ASCII 字符，您只需要 8 位2^8 = 256（其中^表示求幂）。

于 2012-09-15T19:24:04.060 回答