BAEL-4523 - Added code example for article to find the largest power of 2 that is less than the given number (eugenp#9840)

KarthikBalaraman · web-flow · commit 230fd8d849a4 · 2020-08-27T18:32:43.000+01:00
diff --git a/core-java-modules/core-java-lang-math-2/src/main/java/com/baeldung/algorithms/largestpowerof2/LargestPowerOf2.java b/core-java-modules/core-java-lang-math-2/src/main/java/com/baeldung/algorithms/largestpowerof2/LargestPowerOf2.java
@@ -0,0 +1,60 @@
+package com.baeldung.algorithms.largestpowerof2;
+
+import org.nd4j.linalg.io.Assert;
+
+public class LargestPowerOf2 {
+    public long findLargestPowerOf2LessThanTheGivenNumber(long input) {
+        Assert.isTrue(input > 1, "Invalid input");
+
+        long firstPowerOf2 = 1;
+        long nextPowerOf2 = 2;
+
+        while (nextPowerOf2 < input) {
+            firstPowerOf2 = nextPowerOf2;
+            nextPowerOf2 = nextPowerOf2 * 2;
+        }
+        return firstPowerOf2;
+    }
+
+    public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(long input) {
+        Assert.isTrue(input > 1, "Invalid input");
+
+        long temp = input;
+        if (input % 2 == 0) {
+            temp = input - 1;
+        }
+
+        // Find log base 2 of a given number
+        long power = (long) (Math.log(temp) / Math.log(2));
+        long result = (long) Math.pow(2, power);
+
+        return result;
+    }
+
+    public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(long input) {
+        Assert.isTrue(input > 1, "Invalid input");
+        long result = 1;
+        for (long i = input - 1; i > 1; i--) {
+            if ((i & (i - 1)) == 0) {
+                result = i;
+                break;
+            }
+        }
+        return result;
+    }
+
+    public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(long input) {
+        Assert.isTrue(input > 1, "Invalid input");
+        long result = 1;
+        long powerOf2;
+
+        for (long i = 0; i < Long.BYTES * 8; i++) {
+            powerOf2 = 1 << i;
+            if (powerOf2 >= input) {
+                break;
+            }
+            result = powerOf2;
+        }
+        return result;
+    }
+}
diff --git a/core-java-modules/core-java-lang-math-2/src/test/java/com/baeldung/algorithms/largestpowerof2/LargestPowerOf2UnitTest.java b/core-java-modules/core-java-lang-math-2/src/test/java/com/baeldung/algorithms/largestpowerof2/LargestPowerOf2UnitTest.java
@@ -0,0 +1,67 @@
+package com.baeldung.algorithms.largestpowerof2;
+
+import java.util.Arrays;
+import java.util.Collection;
+
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class LargestPowerOf2UnitTest {
+    private long input;
+    private long expectedResult;
+
+    public LargestPowerOf2UnitTest(long input, long expectedResult) {
+        this.input = input;
+        this.expectedResult = expectedResult;
+    }
+
+    @Parameterized.Parameters(name = "{index}: verifyLargestPowerOf2LessThanTheGivenNumber({0}) = {1}")
+    public static Collection<Object[]> data() {
+        return Arrays.asList(new Object[][] { { 2, 1 }, { 4, 2 }, { 500, 256 }, { 512, 256 }, { 1050, 1024 } });
+    }
+
+    @Test
+    public void givenValidInput_verifyLargestPowerOf2LessThanTheGivenNumber() {
+        LargestPowerOf2 largestPowerOf2 = new LargestPowerOf2();
+
+        long result = largestPowerOf2.findLargestPowerOf2LessThanTheGivenNumber(input);
+
+        Assert.assertEquals(expectedResult, result);
+    }
+
+    @Test
+    public void givenValidInput_verifyLargestPowerOf2LessThanTheGivenNumberUsingLogBase2() {
+        LargestPowerOf2 largestPowerOf2 = new LargestPowerOf2();
+
+        long result = largestPowerOf2.findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(input);
+
+        Assert.assertEquals(expectedResult, result);
+    }
+
+    @Test
+    public void givenValidInput_verifyLargestPowerOf2LessThanTheGivenNumberBitwiseAnd() {
+        LargestPowerOf2 largestPowerOf2 = new LargestPowerOf2();
+
+        long result = largestPowerOf2.findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(input);
+
+        Assert.assertEquals(expectedResult, result);
+    }
+
+    @Test
+    public void givenValidInput_verifyLargestPowerOf2LessThanTheGivenNumberBitShiftApproach() {
+        LargestPowerOf2 largestPowerOf2 = new LargestPowerOf2();
+
+        long result = largestPowerOf2.findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(input);
+
+        Assert.assertEquals(expectedResult, result);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void givenInvalidInput_ShouldThrowException() {
+        LargestPowerOf2 largestPowerOf2 = new LargestPowerOf2();
+        largestPowerOf2.findLargestPowerOf2LessThanTheGivenNumber(1);
+    }
+}
