java - 使用位操作验证 ascii 字符串是否包含唯一字符，而不使用其他数据结构

Question

我试图解决这个问题，但是当输入在输入字符串中包含相同字母的小版本和大写版本时，我的程序失败，例如：-Test，Abca。

// Assuming Input to be an ASCII String i.e a total of 128 unique characters, which map to the numbers 0–127.

public class Q1_1 {
    public static void main(String[] args) {
        long firstHalf = 0; // 0 - 63
        long secondHalf = 0; // 64 - 127
        Scanner sc = new Scanner(System.in);
        String x = sc.nextLine();
        for(int i = 0; i < x.length(); i++) {
            byte b = (byte) x.charAt(i);
            System.out.println((char) b + " - " + b);
            if(b < 63) { // search firstHalf
                System.out.println("First Half");
                long mask = 1 << b;
                if((firstHalf & mask) == 0) { // unique character is encountered
                    firstHalf |= mask;
                } else {
                    System.out.println("String contains Duplicate Character");
                    return;
                }
            } else if(b > 63 && b < 128) {
                System.out.println("Second Half");
                long mask = 1 << (b - 64);
                if((secondHalf & mask) == 0) {  // unique character is encountered
                    secondHalf |= mask;
                } else {
                    System.out.println("String contains Duplicate Character");
                    return;
                }
            }
        }
        System.out.println("ASCII String contains only unique character");
    }
}

正如您在输出中清楚地看到的那样，程序在遇到“t”时停止。

标签： javaalgorithmbit-manipulation

Answer 1

这是因为位移：

(1 << (b - 64))

用int完成，不长，所以移位在 32 位后重复。

使用以下方法使其长时间移动：

(1L << (b - 64))