解释使用位向量用于确定是否所有的字符都是唯一 [英] Explain the use of a bit vector for determining if all characters are unique

问题描述

我感到困惑的一个位向量是如何工作的做到这一点（不是太熟悉位向量）。这是考虑到code。可能有人请走在我通过这个？

I am confused about how a bit vector would work to do this (not too familiar with bit vectors). Here is the code given. Could someone please walk me through this?

public static boolean isUniqueChars(String 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;
}

特别是，什么是检查在做什么？

推荐答案

INT检查在这里用作位的存储。在整数值的每一位都可以视为一个标志，所以最终 INT 是一组位（标志）。在code状态中的每个位是否与位的索引字符字符串或没有被发现。你可以使用位向量出于同样的原因，而不是 INT 。它们之间有两点不同：

int checker is used here as a storage for bits. Every bit in integer value can be treated as a flag, so eventually int is an array of bits (flag). Each bit in your code states whether the character with bit's index was found in string or not. You could use bit vector for the same reason instead of int. There are two differences between them:

• 尺寸即可。 INT 有固定的大小，通常为4个字节，这意味着8 * 4 = 32位（标志）。位向量通常可以是不同的大小，或者就应该在构造函数中的大小。

• Size. int has fixed size, usually 4 bytes which means 8*4=32 bits (flags). Bit vector usually can be of different size or you should specify the size in constructor.

API 。随着位向量，你将有更容易阅读code，可能是这样的：

API. With bit vectors you will have easier to read code, probably something like this:

vector.SetFlag（4，真正的）; //索引设置标志4为真

为 INT 您将有较低级别位逻辑code：

for int you will have lower-level bit logic code:

检查| =（1 <<;＆LT; 5）;在指数5至真//设置标志

也大抵 INT 可能是有点快，因为有位操作是非常低的水平，并可以执行AS-是CPU。位向量允许写那么一点点神秘code，而不是加上它可以存储更多的标志。

Also probably int may be a little bit faster, because operations with bits are very low level and can be executed as-is by CPU. BitVector allows writing a little bit less cryptic code instead plus it can store more flags.

有关将来参考：比特向量也被称为BITSET或bitArray。这里有一些链接，为不同的语言/平台，这个数据结构：

For future reference: bit vector is also known as bitSet or bitArray. Here are some links to this data structure for different languages/platforms:

• CPP：位集合


• Java的：位集合


• C＃：<一href=\"http://msdn.microsoft.com/en-us/library/system.collections.specialized.bitvector32.aspx\">BitVector32和 BitArray

• CPP: BitSet
• Java: BitSet
• C#: BitVector32 and BitArray

这篇关于解释使用位向量用于确定是否所有的字符都是唯一的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！