Add Highest Set Bit algorithm (TheAlgorithms#4330)

BamaCharanChhandogi · web-flow · commit fc693e8b514f · 2023-09-05T20:19:23.000Z
diff --git a/src/main/java/com/thealgorithms/bitmanipulation/HighestSetBit.java b/src/main/java/com/thealgorithms/bitmanipulation/HighestSetBit.java
@@ -0,0 +1,32 @@
+package com.thealgorithms.bitmanipulation;
+import java.util.Optional;
+
+/**
+ * Find Highest Set Bit
+ * This class provides a function calculating the position (or index)
+ * of the most significant bit being set to 1 in a given integer.
+ * @author Bama Charan Chhandogi (https://github.com/BamaCharanChhandogi)
+ */
+
+public final class HighestSetBit {
+    private HighestSetBit() {
+    }
+
+    public final static Optional<Integer> findHighestSetBit(int num) {
+        if (num < 0) {
+            throw new IllegalArgumentException("Input cannot be negative");
+        }
+
+        if (num == 0) {
+            return Optional.empty();
+        }
+
+        int position = 0;
+        while (num > 0) {
+            num >>= 1;
+            position++;
+        }
+
+        return Optional.of(position - 1);
+    }
+}
diff --git a/src/test/java/com/thealgorithms/bitmanipulation/HighestSetBitTest.java b/src/test/java/com/thealgorithms/bitmanipulation/HighestSetBitTest.java
@@ -0,0 +1,37 @@
+package com.thealgorithms.bitmanipulation;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+/**
+ * Test case for Highest Set Bit
+ * @author Bama Charan Chhandogi (https://github.com/BamaCharanChhandogi)
+ */
+
+class HighestSetBitTest {
+
+    @Test
+    void testHighestSetBit() {
+        assertFalse(HighestSetBit.findHighestSetBit(0).isPresent());
+        assertEquals(0, HighestSetBit.findHighestSetBit(1).get());
+        assertEquals(1, HighestSetBit.findHighestSetBit(2).get());
+        assertEquals(1, HighestSetBit.findHighestSetBit(3).get());
+        assertEquals(2, HighestSetBit.findHighestSetBit(4).get());
+        assertEquals(2, HighestSetBit.findHighestSetBit(5).get());
+        assertEquals(2, HighestSetBit.findHighestSetBit(7).get());
+        assertEquals(3, HighestSetBit.findHighestSetBit(8).get());
+        assertEquals(3, HighestSetBit.findHighestSetBit(9).get());
+        assertEquals(3, HighestSetBit.findHighestSetBit(15).get());
+        assertEquals(4, HighestSetBit.findHighestSetBit(16).get());
+        assertEquals(4, HighestSetBit.findHighestSetBit(17).get());
+        assertEquals(4, HighestSetBit.findHighestSetBit(31).get());
+        assertEquals(5, HighestSetBit.findHighestSetBit(32).get());
+        assertEquals(5, HighestSetBit.findHighestSetBit(33).get());
+        assertEquals(7, HighestSetBit.findHighestSetBit(255).get());
+        assertEquals(8, HighestSetBit.findHighestSetBit(256).get());
+        assertEquals(8, HighestSetBit.findHighestSetBit(511).get());
+        assertEquals(9, HighestSetBit.findHighestSetBit(512).get());
+        assertThrows(IllegalArgumentException.class, () -> HighestSetBit.findHighestSetBit(-37));
+    }
+}
