Skip to content

Commit 4e1e7e9

Browse files
kahgohkahgoh
authored
Add bit manipulation concept (exercism#2649)
1 parent bea1013 commit 4e1e7e9

16 files changed

Lines changed: 555 additions & 2 deletions

File tree

‎concepts/bit-manipulation/.meta/config.json‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
{
2+
"blurb": "Perform bitwise operations using the bitwise operators.",
3+
"authors": [
4+
"kahgoh"
5+
],
6+
"contributors": []
7+
}

‎concepts/bit-manipulation/about.md‎

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
# About Bit Manipulation
2+
3+
Java has operators for manipulating the bits of an [integral type][integral-type] (a `byte`, `short`, `int`, `long` or `char`).
4+
5+
## Shift operators
6+
7+
Use `<<` to shift bits to the left and `>>` to shift to the right.
8+
9+
```java
10+
// Shift two places to the left
11+
0b0000_1011 << 2;
12+
// # => 0b0010_1100
13+
14+
// Shift two places to the right
15+
0b0000_1011 >> 2;
16+
// # => 0b0000_0010
17+
```
18+
19+
`>>` is also called a [signed shift or arithmetic shift][arithmetic-shift] operator because the bit it is inserts is same as its sign bit.
20+
This is the left most bit and is 0 if the value is positive or 1 when negative.
21+
Shifting to the left with `<<` always inserts 0s on the right hand side.
22+
23+
```java
24+
// Shift 2 places to the right preserves the sign
25+
// The binary value is two's complement of 0b0000_0110 (or 0x00000026), so the binary representation will be
26+
// 1000_0000_0000_0000_0000_0000_0010_0110
27+
int value = -0x7FFFFFDA;
28+
29+
// Shift two places to the right, preserving the sign bit
30+
value >> 2;
31+
// # => 1110_0000_0000_0000_0000_0000_0000_1001
32+
```
33+
34+
Use `>>>` instead when 0s are to be inserted when shifting to the right.
35+
Inserting 0s when shifting is also known as a [logical shift][logical-shift].
36+
37+
```java
38+
// Shift two places to the right, inserting 0s on the left
39+
value >>> 2;
40+
// # => 0010_0000_0000_0000_0000_0000_0000_1001
41+
```
42+
43+
## Bitwise Operations
44+
45+
### Bitwise AND
46+
47+
The bitwise AND (`&`) operator takes two values and performs an AND on each bit.
48+
It compares each bit from the first value with the bit in the same position from the second value.
49+
If they are both 1, then the result's bit is 1.
50+
Otherwise, the result's bit is 0.
51+
52+
```java
53+
0b0110_0101 & 0b0011_1100;
54+
// # => 0b0010_0100
55+
```
56+
57+
### Bitwise OR
58+
59+
The bitwise OR (`|`) operator takes two values and performs an OR on each bit.
60+
It compares each bit from the first value with the bit in thes same position from the second value.
61+
If either bit is 1, the result's bit is 1.
62+
Otherwise, it is 0.
63+
64+
```java
65+
0b0110_0101 | 0b0011_1100;
66+
// # => 0b0111_1101
67+
```
68+
69+
### Bitwise XOR
70+
71+
The bitwise XOR operator (`^`) performs a bitwise XOR on two values.
72+
Like the bitwise AND and bitwise OR operators, it compares each bit from the first value against the bit in the same position from the second value.
73+
If only one of them is 1, the resulting bit is 1.
74+
Otherwise, it is 0.
75+
76+
```java
77+
0b0110_0101 ^ 0b0011_1100;
78+
// # => 0b0101_1001
79+
```
80+
81+
### Bitwise NOT(`~`)
82+
83+
Lastly, the bitwise NOT operator (`~`) flips each bit.
84+
Unlike the earlier operators, this is a unary operator, acting only on one value.
85+
86+
```java
87+
~0b0110_0101;
88+
// # => 0b1001_1010
89+
```
90+
91+
[integral-type]: https://docs.oracle.com/javase/specs/jls/se21/html/jls-4.html#jls-4.2
92+
[arithmetic-shift]: https://en.wikipedia.org/wiki/Arithmetic_shift
93+
[logical-shift]: https://en.wikipedia.org/wiki/Logical_shift

‎concepts/bit-manipulation/introduction.md‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
# Introduction to Bit Manipulation
2+
3+
Java has operators for manipulating the bits of a `byte`, `short`, `int`, `long` or `char`.
4+
5+
## Shift operators
6+
7+
Use `<<` to shift bits to the left and `>>` to shift to the right.
8+
9+
```java
10+
// Shift two places to the left
11+
0b0000_1011 << 2;
12+
// # => 0b0010_1100
13+
14+
// Shift two places to the right
15+
0b0000_1011 >> 2;
16+
// # => 0b0000_0010
17+
```
18+
19+
The `<<` operator always inserts 0s on the right hand side.
20+
However, `>>` inserts the same bit as the left most bit (1 if the number is negative or 0 if positive).
21+
22+
```java
23+
// Shift 2 places to the right preserves the sign
24+
// This is a negative value, whose binary representation is
25+
// 1000_0000_0000_0000_0000_0000_0010_0110
26+
int value = -0x7FFFFFDA;
27+
28+
// Shift two places to the right, preserving the sign bit
29+
value >> 2;
30+
// # => 1110_0000_0000_0000_0000_0000_0000_1001
31+
```
32+
33+
Use `>>>` instead when 0s are to be inserted when shifting to the right.
34+
35+
```java
36+
// Shift two places to the right, inserting 0s on the left
37+
value >>> 2;
38+
// # => 0010_0000_0000_0000_0000_0000_0000_1001
39+
```
40+
41+
## Bitwise Operations
42+
43+
### Bitwise AND
44+
45+
The bitwise AND (`&`) operator takes two values and performs an AND on each bit.
46+
It compares each bit from the first value with the bit in the same position from the second value.
47+
If they are both 1, then the result's bit is 1.
48+
Otherwise, the result's bit is 0.
49+
50+
```java
51+
0b0110_0101 & 0b0011_1100;
52+
// # => 0b0010_0100
53+
```
54+
55+
### Bitwise OR
56+
57+
The bitwise OR (`|`) operator takes two values and performs an OR on each bit.
58+
It compares each bit from the first value with the bit in thes same position from the second value.
59+
If either bit is 1, the result's bit is 1.
60+
Otherwise, it is 0.
61+
62+
```java
63+
0b0110_0101 | 0b0011_1100;
64+
// # => 0b0111_1101
65+
```
66+
67+
### Bitwise XOR
68+
69+
The bitwise XOR operator (`^`) performs a bitwise XOR on two values.
70+
Like the bitwise AND and bitwise OR operators, it compares each bit from the first value against the bit in the same position from the second value.
71+
If only one of them is 1, the resulting bit is 1.
72+
Otherwise, it is 0.
73+
74+
```java
75+
0b0110_0101 ^ 0b0011_1100;
76+
// # => 0b0101_1001
77+
```
78+
79+
### Bitwise NOT(`~`)
80+
81+
Lastly, the bitwise NOT operator (`~`) flips each bit.
82+
Unlike the earlier operators, this is a unary operator, acting only on one value.
83+
84+
```java
85+
~0b0110_0101;
86+
// # => 0b1001_1010
87+
```

‎concepts/bit-manipulation/links.json‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
[
2+
{
3+
"url": "https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html",
4+
"description": "The Java Tutorials - Bitwise and Bit Shift Operators"
5+
},
6+
{
7+
"url": "https://dev.java/learn/language-basics/using-operators/#bitwise-bitshift",
8+
"description": "Using Operators in Your Programs: Bitwise and Bit Shift Operators"
9+
},
10+
{
11+
"url": "https://dev.java/learn/language-basics/all-operators/#bitwise-bitshift",
12+
"description": "Summary of Operators: Bitwise and Bit Shift Operators"
13+
}
14+
]

‎config.json‎

Lines changed: 20 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -285,6 +285,17 @@
285285
"enums"
286286
],
287287
"status": "active"
288+
},
289+
{
290+
"slug": "secrets",
291+
"name": "secrets",
292+
"uuid": "b6485b16-e94d-41ce-9689-d94b70266f5e",
293+
"concepts": [
294+
"bit-manipulation"
295+
],
296+
"prerequisites": [
297+
"numbers"
298+
]
288299
}
289300
],
290301
"practice": [
@@ -555,7 +566,8 @@
555566
"uuid": "2d5b6404-3315-48c1-892f-b594a960e7a1",
556567
"practices": [],
557568
"prerequisites": [
558-
"numbers"
569+
"numbers",
570+
"bit-manipulation"
559571
],
560572
"difficulty": 3
561573
},
@@ -854,7 +866,8 @@
854866
"practices": [],
855867
"prerequisites": [
856868
"for-loops",
857-
"enums"
869+
"enums",
870+
"bit-manipulation"
858871
],
859872
"difficulty": 5
860873
},
@@ -1783,6 +1796,11 @@
17831796
"slug": "basics",
17841797
"name": "Basics"
17851798
},
1799+
{
1800+
"uuid": "3491358c-26fd-4c08-91c4-a6f76b3ed01a",
1801+
"slug": "bit-manipulation",
1802+
"name": "Bit Manipulation"
1803+
},
17861804
{
17871805
"uuid": "ea12527d-7a9d-461e-93b1-bf639652430e",
17881806
"slug": "booleans",

‎exercises/concept/secrets/.docs/hints.md‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
# Hints
2+
3+
## 1. Shift back the bits
4+
5+
- There are two operators for shifting to the right, but only one will always insert a 0.
6+
7+
## 2. Set some bits
8+
9+
- One of the bit wise operators will always set a bit to 1 where the bits in both values are 1.
10+
11+
## 3. Flip specific bits
12+
13+
- There is an bit operation that will flip a bit where the mask is 1.
14+
15+
## 4. Clear specific bits
16+
17+
- One of the bit operations clears bits where the bit in the mask is 0.
18+
- But you may need to combine it with another operator to clear bits where the mask is 1.

‎exercises/concept/secrets/.docs/instructions.md‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
# Instructions
2+
3+
Your friend has just sent you a message with an important secret.
4+
Not wanting to make it easy for others to read it, the message was encrypted by performing a series of bit manipulations.
5+
You will need to write the methods to help decrypt the message.
6+
7+
## 1. Shift back the bits
8+
9+
The first step in decrypting the message is to undo the shifting from the encryption process by shifting the bits back to the right.
10+
There will be further steps in the decryption process that assume 0s are inserted from the left hand side.
11+
12+
Implement the `Secrets.shiftBack` method that takes a value and the number of places to shift and peforms the shift.
13+
14+
```java
15+
Secrets.shiftBack(0b1001, 2);s
16+
# => 0b0010
17+
```
18+
19+
## 2. Set some bits
20+
21+
Next, there are some bits that need to be set to 1.
22+
23+
Implement the `Secrets.setBits` method that takes a value and a mask and returns the result of setting the bits in value to 1.
24+
A bit from value should be set to 1 where the bit in the mask is also 1.
25+
All other bits should be kept unchanged.
26+
27+
```java
28+
Secrets.setBits(0b0110, 0b0101);
29+
# => 0b0111
30+
```
31+
32+
## 3. Flip specific bits
33+
34+
Some bits are flipped during encryption.
35+
They will need to be flipped back to decrypt the message.
36+
37+
Implement the `Secrets.flipBits` method that takes a value and the mask.
38+
The mask indicates which bits in the value to flip.
39+
If the bit is 1 in mask, the bit is flipped in the value.
40+
All other bits are kept unchanged.
41+
42+
```java
43+
Secrets.flipBits(0b1100, 0b0101)
44+
# => 0b1001
45+
```
46+
47+
## 4. Clear specific bits
48+
49+
Lastly, there are also certain bits that always decrpyt to 0.
50+
51+
Implement the `Secrets.clearBits` method that takes a value and a mask.
52+
The bits in the `value` should be set to 0 where the bit in the mask is 1.
53+
All other bits should be kept unchanged.
54+
55+
```java
56+
Secrets.applyMask(0b0110, 0b0101);
57+
# => 0b0010
58+
```

0 commit comments

Comments
 (0)