How does BitSet's set method work with bits shifting to the left?

user_504807 0
Viewed 62

Java's BitSet class has a method Set that sets a single bit to 1 (=true). The method source code is as follows:

public void set(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    int wordIndex = wordIndex(bitIndex);
    expandTo(wordIndex);

    words[wordIndex] |= (1L << bitIndex); // Restores invariants

    checkInvariants();
}

In addition to the checks, the method's core code is: words[wordIndex] |= (1L << bitIndex). I can clearly see in the assignment that the left part is the specific word that holds the relevant bit. However, I don't understand how the right part (the shifting left of the bit index) cause the setting of the requested (and only it) bit to 1. Could you please explain?

bitset java
3 Answers

1L << bitIndex produces a long, whose bits are all 0s, except for one of the bits. The position of the "1" bit is determined by bitIndex. For example, if bitIndex is 10, then the 11th least significant bit is 1.

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0100 0000 0000

Because the 1 is shifted to the left 10 times. In general, the (bitIndex mod 64 + 1)th least significant bit is the "1" bit.

This mask is then bitwise OR'ed with whatever is in words[wordIndex]. Every bit in words[wordIndex] stays the same because they are OR'ed with 0, except for the one place where it is a "1" in the mask. That bit in words[wordIndex] will become "1" no matter what it was originally, due to how OR works.

user_51335850

There are two parts of interest: 1L << bitIndex and words[wordIndex] |=.

The first part – 1L << bitIndex – shifts a bit some number of spots. Here's a table showing how that plays out with a few different numbers of shifting.

statement decimal binary
1L << 0 1 1
1L << 1 2 10
1L << 2 4 100
1L << 3 8 1000
1L << 4 16 10000

The second part – words[wordIndex] |= – takes whatever value was already at words[wordIndex] and uses bitwise "or" to include whatever bit was isolated from above. If that bit was already set (for that word), this operation wouldn't change anything. If the bit was 0, the "or" operation (|=) would set the bit to 1.

user_113749570

Remember that the left side is being ORed (|) with the bit and the right most bit (or the Least Significant Bit - LSB) is bit 0. An OR operator will set the specified one bit(s) in the source, to the same bits in the target, leaving the other bits unchanged. Here are some examples.

int bits = 1;
System.out.println(Integer.toBinaryString(bits));
bits |= 0b100_0000_0000; // set bit 10 to 1.
System.out.println(Integer.toBinaryString(bits));

prints

1
10000000001
^
bit 10

or do it like this


System.out.println(Integer.toBinaryString(bits));
bits = 1;
// or it can be done this way.
bits |=  1<<10;  // 10 is the bitIndex in bits to set so it is shifted 
                 // left to that position and the result is as before
System.out.println(Integer.toBinaryString(bits));

prints

10000000001
^
bit 10
user_15525340
Related