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

Commit5784a4a

Browse files
committed
Merge branch 'master' into segment-tree
2 parentsc7610d5 +74b93d3 commit5784a4a

File tree

6 files changed

+174
-0
lines changed

6 files changed

+174
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,7 @@ a set of rules that precisely define a sequence of operations.
5050
*[Least Common Multiple](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/least-common-multiple) (LCM)
5151
*[Integer Partition](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/integer-partition)
5252
*[Sieve of Eratosthenes](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/sieve-of-eratosthenes) - finding all prime numbers up to any given limit
53+
*[Is Power of Two](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/is-power-of-two) - check if the number is power of two (naive and bitwise algorithms)
5354
***Sets**
5455
*[Cartesian Product](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/cartesian-product) - product of multiple sets
5556
*[Power Set](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/power-set) - all subsets of a set
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
#Is a power of two
2+
3+
Given a positive integer, write a function to find if it is
4+
a power of two or not.
5+
6+
**Naive solution**
7+
8+
In naive solution we just keep dividing the number by two
9+
unless the number becomes`1` and every time we do so we
10+
check that remainder after division is always`0`. Otherwise
11+
the number can't be a power of two.
12+
13+
**Bitwise solution**
14+
15+
Powers of two in binary form always have just one bit.
16+
The only exception is with a signed integer (e.g. an 8-bit
17+
signed integer with a value of -128 looks like:`10000000`)
18+
19+
```
20+
1: 0001
21+
2: 0010
22+
4: 0100
23+
8: 1000
24+
```
25+
26+
So after checking that the number is greater than zero,
27+
we can use a bitwise hack to test that one and only one
28+
bit is set.
29+
30+
```
31+
number & (number - 1)
32+
```
33+
34+
For example for number`8` that operations will look like:
35+
36+
```
37+
1000
38+
- 0001
39+
----
40+
0111
41+
42+
1000
43+
& 0111
44+
----
45+
0000
46+
```
47+
48+
##References
49+
50+
-[GeeksForGeeks](https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/)
51+
-[Bitwise Solution on Stanford](http://www.graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)
52+
-[Binary number subtraction on YouTube](https://www.youtube.com/watch?v=S9LJknZTyos&t=0s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=66)
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
importisPowerOfTwofrom'../isPowerOfTwo';
2+
3+
describe('isPowerOfTwo',()=>{
4+
it('should throw an exception when trying to apply function to negative number',()=>{
5+
constisNegativePowerOfTwo=()=>{
6+
isPowerOfTwo(-1);
7+
};
8+
9+
expect(isNegativePowerOfTwo).toThrowError();
10+
});
11+
12+
it('should check if the number is made by multiplying twos',()=>{
13+
expect(isPowerOfTwo(0)).toBeFalsy();
14+
expect(isPowerOfTwo(1)).toBeFalsy();
15+
expect(isPowerOfTwo(2)).toBeTruthy();
16+
expect(isPowerOfTwo(3)).toBeFalsy();
17+
expect(isPowerOfTwo(4)).toBeTruthy();
18+
expect(isPowerOfTwo(5)).toBeFalsy();
19+
expect(isPowerOfTwo(6)).toBeFalsy();
20+
expect(isPowerOfTwo(7)).toBeFalsy();
21+
expect(isPowerOfTwo(8)).toBeTruthy();
22+
expect(isPowerOfTwo(10)).toBeFalsy();
23+
expect(isPowerOfTwo(12)).toBeFalsy();
24+
expect(isPowerOfTwo(16)).toBeTruthy();
25+
expect(isPowerOfTwo(31)).toBeFalsy();
26+
expect(isPowerOfTwo(64)).toBeTruthy();
27+
expect(isPowerOfTwo(1024)).toBeTruthy();
28+
expect(isPowerOfTwo(1023)).toBeFalsy();
29+
});
30+
});
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
importisPowerOfTwoBitwisefrom'../isPowerOfTwoBitwise';
2+
3+
describe('isPowerOfTwoBitwise',()=>{
4+
it('should throw an exception when trying to apply function to negative number',()=>{
5+
constisNegativePowerOfTwo=()=>{
6+
isPowerOfTwoBitwise(-1);
7+
};
8+
9+
expect(isNegativePowerOfTwo).toThrowError();
10+
});
11+
12+
it('should check if the number is made by multiplying twos',()=>{
13+
expect(isPowerOfTwoBitwise(0)).toBeFalsy();
14+
expect(isPowerOfTwoBitwise(1)).toBeFalsy();
15+
expect(isPowerOfTwoBitwise(2)).toBeTruthy();
16+
expect(isPowerOfTwoBitwise(3)).toBeFalsy();
17+
expect(isPowerOfTwoBitwise(4)).toBeTruthy();
18+
expect(isPowerOfTwoBitwise(5)).toBeFalsy();
19+
expect(isPowerOfTwoBitwise(6)).toBeFalsy();
20+
expect(isPowerOfTwoBitwise(7)).toBeFalsy();
21+
expect(isPowerOfTwoBitwise(8)).toBeTruthy();
22+
expect(isPowerOfTwoBitwise(10)).toBeFalsy();
23+
expect(isPowerOfTwoBitwise(12)).toBeFalsy();
24+
expect(isPowerOfTwoBitwise(16)).toBeTruthy();
25+
expect(isPowerOfTwoBitwise(31)).toBeFalsy();
26+
expect(isPowerOfTwoBitwise(64)).toBeTruthy();
27+
expect(isPowerOfTwoBitwise(1024)).toBeTruthy();
28+
expect(isPowerOfTwoBitwise(1023)).toBeFalsy();
29+
});
30+
});
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/**
2+
*@param {number} number
3+
*@return {boolean}
4+
*/
5+
exportdefaultfunctionisPowerOfTwo(number){
6+
// Don't work with negative numbers.
7+
if(number<0){
8+
thrownewError('Please provide positive number');
9+
}
10+
11+
// 0 and 1 are not powers of two.
12+
if(number<=1){
13+
returnfalse;
14+
}
15+
16+
// Let's find out if we can divide the number by two
17+
// many times without remainder.
18+
letdividedNumber=number;
19+
while(dividedNumber!==1){
20+
if(dividedNumber%2!==0){
21+
// For every case when remainder isn't zero we can say that this number
22+
// couldn't be a result of power of two.
23+
returnfalse;
24+
}
25+
26+
dividedNumber/=2;
27+
}
28+
29+
returntrue;
30+
}
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/**
2+
*@param {number} number
3+
*@return {boolean}
4+
*/
5+
exportdefaultfunctionisPowerOfTwoBitwise(number){
6+
// Don't work with negative numbers.
7+
if(number<0){
8+
thrownewError('Please provide positive number');
9+
}
10+
11+
// 0 and 1 are not powers of two.
12+
if(number<=1){
13+
returnfalse;
14+
}
15+
16+
/*
17+
* Powers of two in binary look like this:
18+
* 1: 0001
19+
* 2: 0010
20+
* 4: 0100
21+
* 8: 1000
22+
*
23+
* Note that there is always exactly 1 bit set. The only exception is with a signed integer.
24+
* e.g. An 8-bit signed integer with a value of -128 looks like:
25+
* 10000000
26+
*
27+
* So after checking that the number is greater than zero, we can use a clever little bit
28+
* hack to test that one and only one bit is set.
29+
*/
30+
return(number&(number-1))===0;
31+
}

0 commit comments

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