Repository: TheAlgorithms/Java
Pull request #5865 (2024-10-16 03:44:18)

feat: Add `NextHigherSameBitCount` new algorithm with Junit tests
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 28bd525b..7bc9cea3 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -41,6 +41,7 @@
             * [IsPowerTwo](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/IsPowerTwo.java)
             * [LowestSetBit](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/LowestSetBit.java)
             * [ModuloPowerOfTwo](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/ModuloPowerOfTwo.java)
+            * [NextHigherSameBitCount](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/NextHigherSameBitCount.java)
             * [NonRepeatingNumberFinder](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/NonRepeatingNumberFinder.java)
             * [NumberAppearingOddTimes](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/NumberAppearingOddTimes.java)
             * [NumbersDifferentSigns](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/NumbersDifferentSigns.java)
@@ -744,6 +745,7 @@
             * [IsPowerTwoTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/IsPowerTwoTest.java)
             * [LowestSetBitTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/LowestSetBitTest.java)
             * [ModuloPowerOfTwoTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/ModuloPowerOfTwoTest.java)
+            * [NextHigherSameBitCountTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/NextHigherSameBitCountTest.java)
             * [NonRepeatingNumberFinderTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/NonRepeatingNumberFinderTest.java)
             * [NumberAppearingOddTimesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/NumberAppearingOddTimesTest.java)
             * [NumbersDifferentSignsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/NumbersDifferentSignsTest.java)
diff --git a/src/main/java/com/thealgorithms/bitmanipulation/NextHigherSameBitCount.java b/src/main/java/com/thealgorithms/bitmanipulation/NextHigherSameBitCount.java
new file mode 100644
index 00000000..6a764d80
--- /dev/null
+++ b/src/main/java/com/thealgorithms/bitmanipulation/NextHigherSameBitCount.java
@@ -0,0 +1,30 @@
+package com.thealgorithms.bitmanipulation;
+
+/**
+ * This class provides a method to find the next higher number
+ * with the same number of set bits as the given number.
+ *
+ * @author Hardvan
+ */
+public final class NextHigherSameBitCount {
+    private NextHigherSameBitCount() {
+    }
+
+    /**
+     * Finds the next higher integer with the same number of set bits.
+     * Steps:
+     * 1. Find {@code c}, the rightmost set bit of {@code n}.
+     * 2. Find {@code r}, the rightmost set bit of {@code n + c}.
+     * 3. Swap the bits of {@code r} and {@code n} to the right of {@code c}.
+     * 4. Shift the bits of {@code r} and {@code n} to the right of {@code c} to the rightmost.
+     * 5. Combine the results of steps 3 and 4.
+     *
+     * @param n the input number
+     * @return the next higher integer with the same set bit count
+     */
+    public static int nextHigherSameBitCount(int n) {
+        int c = n & -n;
+        int r = n + c;
+        return (((r ^ n) >> 2) / c) | r;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/bitmanipulation/NextHigherSameBitCountTest.java b/src/test/java/com/thealgorithms/bitmanipulation/NextHigherSameBitCountTest.java
new file mode 100644
index 00000000..c8fb9ef2
--- /dev/null
+++ b/src/test/java/com/thealgorithms/bitmanipulation/NextHigherSameBitCountTest.java
@@ -0,0 +1,22 @@
+package com.thealgorithms.bitmanipulation;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+class NextHigherSameBitCountTest {
+
+    @ParameterizedTest
+    @CsvSource({
+        "5, 6", // 101 -> 110
+        "7, 11", // 0111 -> 1011
+        "3, 5", // 011 -> 101
+        "12, 17", // 001100 -> 010001
+        "15, 23" // 01111 -> 10111
+    })
+    void
+    testNextHigherSameBitCount(int input, int expected) {
+        assertEquals(expected, NextHigherSameBitCount.nextHigherSameBitCount(input));
+    }
+}