Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf8ffacd

Browse files
feat: add Gray Code generation (TheAlgorithms#1425)
---------Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
1 parentda0ee87 commitf8ffacd

File tree

2 files changed

+61
-0
lines changed

2 files changed

+61
-0
lines changed

‎Bit-Manipulation/GrayCodes.js

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/**
2+
* Generates a Gray code sequence for the given number of bits.
3+
*@param {number} n - The number of bits in the Gray code sequence.
4+
*@returns {number[]} - An array of Gray codes in binary format.
5+
*@description
6+
* Gray codes are binary sequences in which two successive values differ in only one bit.
7+
* This function generates a Gray code sequence of length 2^n for the given number of bits.
8+
*
9+
* The algorithm follows these steps:
10+
*
11+
* 1. Initialize an array `grayCodes` to store the Gray codes. Start with [0, 1] for n = 1.
12+
* 2. Iterate from 1 to n:
13+
* a. Calculate `highestBit` as 2^i, where `i` is the current iteration index.
14+
* b. Iterate in reverse order through the existing Gray codes:
15+
* - For each Gray code `code`, add `highestBit | code` to `grayCodes`.
16+
* - This operation flips a single bit in each existing code, creating new codes.
17+
* 3. Return the `grayCodes` array containing the Gray codes in decimal representation.
18+
*
19+
*resources: [GFG](https://www.geeksforgeeks.org/generate-n-bit-gray-codes/)
20+
*@example
21+
* const n = 3;
22+
* const grayCodes = generateGrayCodes(n);
23+
* // grayCodes will be [0, 1, 3, 2, 6, 7, 5, 4] for n=3.
24+
*/
25+
functiongenerateGrayCodes(n){
26+
if(n<=0){
27+
return[0]
28+
}
29+
30+
constgrayCodes=[0,1]
31+
32+
for(leti=1;i<n;i++){
33+
consthighestBit=1<<i
34+
for(letj=grayCodes.length-1;j>=0;j--){
35+
grayCodes.push(highestBit|grayCodes[j])
36+
}
37+
}
38+
39+
returngrayCodes
40+
}
41+
42+
export{generateGrayCodes}
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
import{generateGrayCodes}from'../GrayCodes.js'
2+
3+
describe('Gray codes',()=>{
4+
test.each([
5+
[0,[0b0]],
6+
[1,[0b0,0b1]],
7+
[2,[0b00,0b01,0b11,0b10]],
8+
[3,[0b000,0b001,0b011,0b010,0b110,0b111,0b101,0b100]],
9+
[
10+
4,
11+
[
12+
0b0000,0b0001,0b0011,0b0010,0b0110,0b0111,0b0101,0b0100,0b1100,
13+
0b1101,0b1111,0b1110,0b1010,0b1011,0b1001,0b1000
14+
]
15+
]
16+
])('n = %i -> %j',(n,expected)=>{
17+
expect(generateGrayCodes(n)).toEqual(expected)
18+
})
19+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp