解释使用位向量来确定所有字符是否都是唯一的

Question

我很困惑有点矢量如何工作(不太熟悉位向量).这是给出的代码.有人可以带我走过这个吗？

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;
}

特别是,checker做什么？

Answer 1

我有一个潜行的怀疑,你从我正在阅读的同一本书中得到这个代码......这里的代码本身并不像运算符 - | =,&,和<<通常不常用的那样神秘我们外行 - 作者没有花费额外的时间来解释这个过程,也不知道这里涉及的实际机制是什么.我在开始时对这个帖子的前一个答案感到满意,但只是在抽象层面上.我回过头来,因为我觉得需要更具体的解释 - 缺乏一个总是让我感到不安.

这个运算符<<是一个左按位移位器,它采用该数字或操作数的二进制表示,并将其移动到操作数或数字指定的许多位置,如十进制数字中的十进制数字.我们乘以基数2 - 当我们向上移动但是许多地方不是基数10-因此右边的数字是指数而左边的数字是2的基数倍.

这个运算符| =取左边的操作数和/或右边的操作数 - 这一个 - '&'和左边和右边的两个操作数的位.

所以我们这里有一个哈希表,每当检查器得到或者checker |= (1 << val)带有指定的字母二进制值(或者它被设置为真的相应位)时,它就以32位二进制数存储.字符的值与checker(checker & (1 << val)) > 0)一起使用 - 如果它大于0,我们知道我们有一个dupe-因为两个相同的位设置为true并且将一起返回true或'1'.

有26个二进制位置,每个位置对应一个小写字母 - 作者确实说假设字符串只包含小写字母 - 这是因为我们只剩下6个(在32位整数中)剩下要消耗的位置 - 而不是我们得到一个碰撞

00000000000000000000000000000001 a 2^0

00000000000000000000000000000010 b 2^1

00000000000000000000000000000100 c 2^2

00000000000000000000000000001000 d 2^3

00000000000000000000000000010000 e 2^4

00000000000000000000000000100000 f 2^5

00000000000000000000000001000000 g 2^6

00000000000000000000000010000000 h 2^7

00000000000000000000000100000000 i 2^8

00000000000000000000001000000000 j 2^9

00000000000000000000010000000000 k 2^10

00000000000000000000100000000000 l 2^11

00000000000000000001000000000000 m 2^12

00000000000000000010000000000000 n 2^13

00000000000000000100000000000000 o 2^14

00000000000000001000000000000000 p 2^15

00000000000000010000000000000000 q 2^16

00000000000000100000000000000000 r 2^17

00000000000001000000000000000000 s 2^18

00000000000010000000000000000000 t 2^19

00000000000100000000000000000000 u 2^20

00000000001000000000000000000000 v 2^21

00000000010000000000000000000000 w 2^22

00000000100000000000000000000000 x 2^23

00000001000000000000000000000000 y 2^24

00000010000000000000000000000000 z 2^25

因此,对于输入字符串'azya',我们一步一步地移动

字符串'a'

a      =00000000000000000000000000000001
checker=00000000000000000000000000000000

checker='a' or checker;
// checker now becomes = 00000000000000000000000000000001
checker=00000000000000000000000000000001

a and checker=0 no dupes condition

字符串'az'

checker=00000000000000000000000000000001
z      =00000010000000000000000000000000

z and checker=0 no dupes 

checker=z or checker;
// checker now becomes 00000010000000000000000000000001  

字符串'azy'

checker= 00000010000000000000000000000001    
y      = 00000001000000000000000000000000 

checker and y=0 no dupes condition 

checker= checker or y;
// checker now becomes = 00000011000000000000000000000001

字符串'azya'

checker= 00000011000000000000000000000001
a      = 00000000000000000000000000000001

a and checker=1 we have a dupe

现在,它宣布重复

Answer 2

int checker在这里用作比特的存储.整数值中的每个位都可以视为一个标志,因此最终int是一个位数组(标志).代码中的每个位都表明是否在字符串中找到了具有位索引的字符.你可以使用位向量而不是int.它们之间有两个不同之处:

• 大小.int具有固定大小,通常为4个字节,这意味着8*4 = 32位(标志).位向量通常可以是不同的大小,或者您应该在构造函数中指定大小.

• API.使用位向量,您将更容易阅读代码,可能是这样的:

  vector.SetFlag(4, true); // set flag at index 4 as true

  因为int你将有更低级别的位逻辑代码:

  checker |= (1 << 5); // set flag at index 5 to true

也可能int更快一点,因为具有位的操作是非常低的级别并且可以由CPU按原样执行.BitVector允许写一些不那么神秘的代码,而且它可以存储更多的标志.

供将来参考:位向量也称为bitSet或bitArray.以下是针对不同语言/平台的此数据结构的一些链接:

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

Answer 3

我还假设你的例子来自Cracking The Code Interview,我的回答与这个背景有关.

为了使用这个算法来解决问题,我们不得不承认我们只会将字符从a传递给z(小写).

因为只有26个字母,并且这些字母在我们使用的编码表中正确排序,这保证了所有潜在的差异str.charAt(i) - 'a'将低于32(int变量的大小checker).

正如Snowbear所解释的那样,我们将把checker变量用作比特数组.让我们举一个例子:

让我们说吧 str equals "test"

• 第一次通过(i = t)

checker == 0(00000000000000000000000000000000)

In ASCII, val = str.charAt(i) - 'a' = 116 - 97 = 19
What about 1 << val ?
1          == 00000000000000000000000000000001
1 << 19    == 00000000000010000000000000000000
checker |= (1 << val) means checker = checker | (1 << val)
so checker = 00000000000000000000000000000000 | 00000000000010000000000000000000
checker == 524288 (00000000000010000000000000000000)

• 第二遍(i = e)

检查器== 524288(000000000000100000000000000000000000)

val = 101 - 97 = 4
1          == 00000000000000000000000000000001
1 << 4     == 00000000000000000000000000010000
checker |= (1 << val) 
so checker = 00000000000010000000000000000000 | 00000000000000000000000000010000
checker == 524304 (00000000000010000000000000010000)

等等......直到我们通过条件找到特定字符的检查器中已设置的位

(checker & (1 << val)) > 0

希望能帮助到你

Answer 4

我认为所有这些答案都解释了它是如何工作的,但是我想通过重命名一些变量,添加其他变量并添加注释来给出我对如何更好地看到它的意见:

public static boolean isUniqueChars(String str) {

    /*
    checker is the bit array, it will have a 1 on the character index that
    has appeared before and a 0 if the character has not appeared, you
    can see this number initialized as 32 0 bits:
    00000000 00000000 00000000 00000000
     */
    int checker = 0;

    //loop through each String character
    for (int i = 0; i < str.length(); ++i) {
        /*
        a through z in ASCII are charactets numbered 97 through 122, 26 characters total
        with this, you get a number between 0 and 25 to represent each character index
        0 for 'a' and 25 for 'z'

        renamed 'val' as 'characterIndex' to be more descriptive
         */
        int characterIndex = str.charAt(i) - 'a'; //char 'a' would get 0 and char 'z' would get 26

        /*
        created a new variable to make things clearer 'singleBitOnPosition'

        It is used to calculate a number that represents the bit value of having that 
        character index as a 1 and the rest as a 0, this is achieved
        by getting the single digit 1 and shifting it to the left as many
        times as the character index requires
        e.g. character 'd'
        00000000 00000000 00000000 00000001
        Shift 3 spaces to the left (<<) because 'd' index is number 3
        1 shift: 00000000 00000000 00000000 00000010
        2 shift: 00000000 00000000 00000000 00000100
        3 shift: 00000000 00000000 00000000 00001000

        Therefore the number representing 'd' is
        00000000 00000000 00000000 00001000

         */
        int singleBitOnPosition = 1 << characterIndex;

        /*
        This peforms an AND between the checker, which is the bit array
        containing everything that has been found before and the number
        representing the bit that will be turned on for this particular
        character. e.g.
        if we have already seen 'a', 'b' and 'd', checker will have:
        checker = 00000000 00000000 00000000 00001011
        And if we see 'b' again:
        'b' = 00000000 00000000 00000000 00000010

        it will do the following:
        00000000 00000000 00000000 00001011
        & (AND)
        00000000 00000000 00000000 00000010
        -----------------------------------
        00000000 00000000 00000000 00000010

        Since this number is different than '0' it means that the character
        was seen before, because on that character index we already have a 
        1 bit value
         */
        if ((checker & singleBitOnPosition) > 0) {
            return false;
        }

        /* 
        Remember that 
        checker |= singleBitOnPosition is the same as  
        checker = checker | singleBitOnPosition
        Sometimes it is easier to see it expanded like that.

        What this achieves is that it builds the checker to have the new 
        value it hasnt seen, by doing an OR between checker and the value 
        representing this character index as a 1. e.g.
        If the character is 'f' and the checker has seen 'g' and 'a', the 
        following will happen

        'f' = 00000000 00000000 00000000 00100000
        checker(seen 'a' and 'g' so far) = 00000000 00000000 00000000 01000001

        00000000 00000000 00000000 00100000
        | (OR)
        00000000 00000000 00000000 01000001
        -----------------------------------
        00000000 00000000 00000000 01100001

        Therefore getting a new checker as 00000000 00000000 00000000 01100001

         */
        checker |= singleBitOnPosition;
    }
    return true;
}

Answer 5

阅读伊万的上述答案确实对我有所帮助,尽管我会用不同的方式说出来.

的<<在(1 << val)是一个比特移位操作.它需要1(二进制表示为000000001,你喜欢/由内存分配的前一个零)并将它移到左边的val空格.由于我们只假设az并且a每次都减去,因此每个字母的值将为0-25,这将是checker整数布尔表示中右边的字母索引,因为我们将1在checker val时间上向左移动.

在每次检查结束时,我们都会看到|=操作员.这将合并两个二进制数,如果在该索引的任一操作数中存在,则0用1's 替换所有' 1.在这里,这意味着无论1存在于何处(1 << val),都1将被复制到其中checker,而所有checker现有的1将被保留.

正如你可能猜到的,1这里的函数作为true的布尔标志.当我们检查一个字符是否已经在字符串中表示时,我们进行比较checker,在这一点上,它本质上是一个布尔标志(1值)数组,在已经表示的字符的索引处,本质上是一个数组布尔值1,在当前字符的索引处带有标志.

该&操作完成这个检查.与此类似|=,仅当两个操作数都具有该索引时,&运算符才会复制.因此,基本上,只有已经存在的标志也将被复制.在这种情况下,这意味着只有当前字符已经被表示时才会在结果中的任何地方出现.如果a 存在于该操作的结果中的任何位置,则返回的布尔值为,并且该方法返回false.1 1checker(1 << val)1checker & (1 << val)1> 0

我猜,这就是为什么位向量也称为位数组.因为,即使它们不是数组数据类型,也可以使用类似于数组的方式来存储布尔标志.

Answer 6

上面已经提供了几个很好的答案.所以我不想重复已经说过的一切.但是我确实想要添加几个东西来帮助完成上述程序,因为我刚刚完成了相同的程序并且有几个问题但是在花了一些时间之后,我对这个程序有了更多的清晰度.

首先,"checker"用于跟踪已在String中遍历的字符,以查看是否有任何字符重复.

现在"checker"是一个int数据类型,因此它只能有32位或4个字节(取决于平台),因此该程序只能在32个字符范围内的字符集中正常工作.这就是原因,这个程序从每个字符中减去'a',以使这个程序只运行小写字符.但是,如果混合使用大小写字符,那么它将无效.

顺便说一句,如果你不从每个字符中减去'a'(见下面的语句),那么这个程序只能用于大写字符串的String或只有小写字符的字符串.因此,上述程序的范围也从小写字符增加到大写字符,但它们不能混合在一起.

int val = str.charAt(i) - 'a'; 

但是我想用Bitwise Operation编写一个通用程序,它应该适用于任何ASCII字符而不用担心大写,小写,数字或任何特殊字符.为此,我们的"检查器"应足够大,以存储256个字符(ASCII字符集大小).但是Java中的int不起作用,因为它只能存储32位.因此在下面的程序中,我使用JDK中可用的BitSet类,它可以在实例化BitSet对象时传递任何用户定义的大小.

这是一个与上面使用Bitwise运算符编写的程序相同的程序,但是该程序适用于具有ASCII字符集中任何字符的String.

public static boolean isUniqueStringUsingBitVectorClass(String s) {

    final int ASCII_CHARACTER_SET_SIZE = 256;

    final BitSet tracker = new BitSet(ASCII_CHARACTER_SET_SIZE);

    // if more than  256 ASCII characters then there can't be unique characters
    if(s.length() > 256) {
        return false;
    }

    //this will be used to keep the location of each character in String
    final BitSet charBitLocation = new BitSet(ASCII_CHARACTER_SET_SIZE);

    for(int i = 0; i < s.length(); i++) {

        int charVal = s.charAt(i);
        charBitLocation.set(charVal); //set the char location in BitSet

        //check if tracker has already bit set with the bit present in charBitLocation
        if(tracker.intersects(charBitLocation)) {
            return false;
        }

        //set the tracker with new bit from charBitLocation
        tracker.or(charBitLocation);

        charBitLocation.clear(); //clear charBitLocation to store bit for character in the next iteration of the loop

    }

    return true;

}

Answer 7

简单解释（下面有JS代码）

• 每个机器码的整数变量是一个32 位数组
• 所有位操作都是 32-bit
• 它们与 OS/CPU 架构或所选语言的数字系统无关，例如DEC64对于 JS。
• 这种重复的发现方法类似于在大小为32的阵列中存储的字符，其中，我们设置0th索引如果发现a字符串中，1st对于b与等等。
• 字符串中的重复字符将占用其相应的位，或者在这种情况下设置为 1。
• Ivan 已经解释过：在之前的答案中该指数计算是如何工作的。

操作总结：

• 在字符的&之间执行AND运算checkerindex
• 内部两者都是 Int-32-Arrays
• 这是这两者之间的逐位运算。
• 检查if操作的输出是1
• 如果 output == 1
  • 该checker变量在两个数组中都设置了特定的第 index-th 位
  • 因此它是重复的。
• 如果 output == 0
  • 目前还没有找到这个角色
  • 在字符的&之间执行OR运算checkerindex
  • 因此，将第 index-th 位更新为 1
  • 将输出分配给 checker

假设：

• 我们假设我们会得到所有小写字符
• 而且，32码就够了
• 因此，我们开始了我们的指数计数从96为参考点考虑ASCII代码aIS97

下面给出的是JavaScript源代码。

function checkIfUniqueChars (str) {

    var checker = 0; // 32 or 64 bit integer variable 

    for (var i = 0; i< str.length; i++) {
        var index = str[i].charCodeAt(0) - 96;
        var bitRepresentationOfIndex = 1 << index;

        if ( (checker & bitRepresentationOfIndex) > 1) {
            console.log(str, false);
            return false;
        } else {
            checker = (checker | bitRepresentationOfIndex);
        }
    }
    console.log(str, true);
    return true;
}

checkIfUniqueChars("abcdefghi");  // true
checkIfUniqueChars("aabcdefghi"); // false
checkIfUniqueChars("abbcdefghi"); // false
checkIfUniqueChars("abcdefghii"); // false
checkIfUniqueChars("abcdefghii"); // false

请注意，在 JS 中，尽管整数是 64 位，但总是在 32 位上进行位操作。

示例： 如果字符串是aa：

// checker is intialized to 32-bit-Int(0)
// therefore, checker is
checker= 00000000000000000000000000000000

我 = 0

str[0] is 'a'
str[i].charCodeAt(0) - 96 = 1

checker 'AND' 32-bit-Int(1) = 00000000000000000000000000000000
Boolean(0) == false

// So, we go for the '`OR`' operation.

checker = checker OR 32-bit-Int(1)
checker = 00000000000000000000000000000001

我 = 1

str[1] is 'a'
str[i].charCodeAt(0) - 96 = 1

checker= 00000000000000000000000000000001
a      = 00000000000000000000000000000001

checker 'AND' 32-bit-Int(1) = 00000000000000000000000000000001
Boolean(1) == true
// We've our duplicate now