что происходит, когда вы сдвигаете Int влево - PullRequest
Новая
       101

что происходит, когда вы сдвигаете Int влево

0 голосов
/ 12 апреля 2020

Я пытаюсь понять часть этого кода, который был создан здесь для создания my_hashset: https://leetcode.com/problems/design-hashset/discuss/548792/Java-solution-faster-than-99

   class HashCode_from_leet {
    int[] bitArr;
    private static final int MAX = 100000;
    private static final int INT_SIZE = Integer.SIZE;

    public HashCode_from_leet() {
        bitArr = new int[MAX / INT_SIZE + 1];
    }

    public void add(int key) {  //pass in 5
        int ind = key / INT_SIZE;  
        int bit = key % INT_SIZE;
        int bitMask = 1 << bit;  //QUESTION: why does bitMask = 32?
        bitArr[ind] |= bitMask;  // QUESTION: what does '|=' mean?
    }

    // NOTE I REMOVED SOME METHODS 

    public boolean contains(int key) {
        int ind = key / INT_SIZE;
        int bit = key % INT_SIZE;
        int bitMask = 1 << bit;
        return (bitArr[ind] & bitMask) != 0;
    }


    public static void main(String[] args) {
        HashCode_from_leet hfl = new HashCode_from_leet();
        hfl.add(5);
        System.out.println(hfl.contains(5));
    }
}

Когда я передаю 5 в add(int key) method bitMask = 32

Я не уверен, почему - я понимаю, << означает сдвиг влево, поэтому мы берем 5 и сдвигаем его влево, но думаем, что это равно 5 * 10 ^ 2? Может ли кто-нибудь помочь мне понять это?

Спасибо

Ответы [ 3 ]

2 голосов
/ 12 апреля 2020

Когда вы shift left целое число от X, например: Z =(Y << X), оно будет выполнять эту операцию в точности: Z = (Y * (2^X))

Когда вы shift right целое число от X, например: Z =(Y >> X), оно будет фактически выполните эту операцию: Z = (Y / (2^X))

1 голос
/ 12 апреля 2020

строка уведомления int bit = key % INT_SIZE; // which is 5 % 32 according to your code

так что теперь bit = 5 // because 5 % 32 = 5

сейчас int bitMask = 1 << bit; // you're saying shit 1 to five bits to left

in 32 bits 1 = 000000000000000000000000000000000001

после нажатия 5 бит влево становится 

000000000000000000000000000000000100000 = 32 //in binary that is why bitmask continas 32

Теперь поговорим о |= операторе

| - побитовом операторе ИЛИ, который вы просто используете в качестве составного присваивания 

bitArr[ind] |= bitMask is similar to bitArr[ind] = bitArr[ind] | bitmask

, например, скажем bitArr[ind] equals 5 and bitmask equals 3

сейчас bitArr[ind] | bitmask означает 5 | 3

он будет выполнять побитовое ИЛИ с двоичным представлением

означает 101 | 011, который становится 111, что составляет 7

1 голос
/ 12 апреля 2020

что происходит, когда вы сдвигаете int влево

Как следует из названия, при сдвиге числа влево на n мест умножается на 2^n. Следующий код поможет вам лучше понять его. 

public class Main {
    public static void main(String[] args) {
        int x = 5;
        System.out.println("In decimal: " + x + ", In Binary: "
                + "0000000000000000".substring(Integer.toBinaryString(x).length()) + Integer.toBinaryString(x));
        int y = x << 1;
        System.out.println("In decimal: " + y + ", In Binary: "
                + "0000000000000000".substring(Integer.toBinaryString(y).length()) + Integer.toBinaryString(y));
        int z = x << 2;
        System.out.println("In decimal: " + z + ", In Binary: "
                + "0000000000000000".substring(Integer.toBinaryString(z).length()) + Integer.toBinaryString(z));
    }
}

Вывод: 

In decimal: 5, In Binary: 0000000000000101
In decimal: 10, In Binary: 0000000000001010
In decimal: 20, In Binary: 0000000000010100

Не стесняйтесь комментировать в случае любых дальнейших сомнений.

...