AK: Add `count_required_bits`

2 files changed, 24 insertions, 0 deletions

diff --git a/AK/BuiltinWrappers.h b/AK/BuiltinWrappers.h
index 1bfdaa5c97..bd0620d1a8 100644
--- a/AK/BuiltinWrappers.h
+++ b/AK/BuiltinWrappers.h
@@ -150,12 +150,23 @@ inline constexpr int bit_scan_forward(IntType value)
 #endif
 }
 
+// Counts the minimum number of bits required to represent the value (i.e. ignoring leading null bits).
+template<Unsigned IntType>
+inline constexpr size_t count_required_bits(IntType value)
+{
+    if (value == 0)
+        return 1;
+
+    return 8 * sizeof(value) - count_leading_zeroes(value);
+}
+
 }
 
 #if USING_AK_GLOBALLY
 using AK::bit_scan_forward;
 using AK::count_leading_zeroes;
 using AK::count_leading_zeroes_safe;
+using AK::count_required_bits;
 using AK::count_trailing_zeroes;
 using AK::count_trailing_zeroes_safe;
 using AK::popcount;
diff --git a/Tests/AK/TestBuiltinWrappers.cpp b/Tests/AK/TestBuiltinWrappers.cpp
index 87b0769b7c..f630e007ea 100644
--- a/Tests/AK/TestBuiltinWrappers.cpp
+++ b/Tests/AK/TestBuiltinWrappers.cpp
@@ -52,3 +52,16 @@ TEST_CASE(wrapped_count_trailing_zeroes)
     EXPECT_EQ(count_trailing_zeroes(static_cast<u64>(1)), 0);
     EXPECT_EQ(count_trailing_zeroes(static_cast<u64>(2)), 1);
 }
+
+TEST_CASE(wrapped_count_required_bits)
+{
+    EXPECT_EQ(count_required_bits(0b0u), 1ul);
+    EXPECT_EQ(count_required_bits(0b1u), 1ul);
+    EXPECT_EQ(count_required_bits(0b10u), 2ul);
+    EXPECT_EQ(count_required_bits(0b11u), 2ul);
+    EXPECT_EQ(count_required_bits(0b100u), 3ul);
+    EXPECT_EQ(count_required_bits(0b111u), 3ul);
+    EXPECT_EQ(count_required_bits(0b1000u), 4ul);
+    EXPECT_EQ(count_required_bits(0b1111u), 4ul);
+    EXPECT_EQ(count_required_bits(NumericLimits<u32>::max()), sizeof(u32) * 8);
+}