serenity icon indicating copy to clipboard operation
serenity copied to clipboard

AK: Fix off by one error in integral ceil_log2()

Open tcl3 opened this issue 9 months ago • 0 comments

Previously, certain values of ceil_log2(x) would be 1 smaller than ceil(log2(x)).

In addition to the test cases I've included in this PR, I also tested ceil_log2() exhaustively (for all u32) with the following test case:

TEST_CASE(ceil_log2_exhaustive)
{
    for (u32 i = 1; i < NumericLimits<u32>::max(); i++)
    {
        if (AK::ceil_log2(i) != ceil(log2(i)))
            FAIL(MUST(String::formatted("AK::ceil_log2(i) != ceil(log2(i) for i = {}, LHS = {}, RHS = {}", i, AK::ceil_log2(i), ceil(log2(i)))));
    }
}

Before this PR, the above test generated the following output:

Running test 'ceil_log2_exhaustive'.
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 1, LHS = 1, RHS = 0
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 3, LHS = 1, RHS = 2
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 6, LHS = 2, RHS = 3
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 12, LHS = 3, RHS = 4
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 24, LHS = 4, RHS = 5
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 48, LHS = 5, RHS = 6
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 96, LHS = 6, RHS = 7
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 192, LHS = 7, RHS = 8
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 384, LHS = 8, RHS = 9
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 768, LHS = 9, RHS = 10
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 1536, LHS = 10, RHS = 11
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 3072, LHS = 11, RHS = 12
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 6144, LHS = 12, RHS = 13
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 12288, LHS = 13, RHS = 14
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 24576, LHS = 14, RHS = 15
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 49152, LHS = 15, RHS = 16
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 98304, LHS = 16, RHS = 17
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 196608, LHS = 17, RHS = 18
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 393216, LHS = 18, RHS = 19
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 786432, LHS = 19, RHS = 20
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 1572864, LHS = 20, RHS = 21
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 3145728, LHS = 21, RHS = 22
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 6291456, LHS = 22, RHS = 23
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 12582912, LHS = 23, RHS = 24
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 25165824, LHS = 24, RHS = 25
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 50331648, LHS = 25, RHS = 26
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 100663296, LHS = 26, RHS = 27
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 201326592, LHS = 27, RHS = 28
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 402653184, LHS = 28, RHS = 29
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 805306368, LHS = 29, RHS = 30
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 1610612736, LHS = 30, RHS = 31
FAIL: /home/tim/repos/serenity/Tests/AK/TestIntegerMath.cpp:82: AK::ceil_log2(i) != ceil(log2(i) for i = 3221225472, LHS = 31, RHS = 32

tcl3 avatar May 13 '24 18:05 tcl3