Test case issue [Fast Bit Calculations]

https://lightoj.com/problem/fast-bit-calculations

I wrote a program in C to solve LOJ-1032 (Fast Bit Calculations). LOJ did not accept my full submission (test 1 passed, test 2 failed). I wrote a separate tool to verify my results, which seem to be accurate.

https://github.com/Skeptx/LightOJ-Problems/blob/main/Submissions/1032.c https://lightoj.com/submission/3087315 (compiled as C++ rather than C)

It passes the public test cases but fails the private ones. I'm not sure what's causing the issue because it's hidden. Verifying my results using the long method:

#include <inttypes.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int main() {
    uint64_t sum = 0;
    for (uint32_t t = 0; t < 2147483648; ++t) { // For each input, from 0 to INT_MAX

        // Calculation to verify result:

        uint32_t N = t;
        uint32_t adj = 0; // Whether previous bit was 1 or 0
        while (N) {
            if (N & adj) { // Check if the previous rightmost bit and current rightmost bit were both set
                ++sum; // Add to number of adjacent bits
            }
            adj = N & 1; // Save whether or not the current rightmost bit is set
            N >>= 1; // Right shift and continue
        }

        // Simple % completion:

        if (t % 21474837 == 0) {
            printf("%d%%\n", t / 21474837);
        }

        // Start of the calculation I used for LightOJ:

        N = t;
        if (t < 4) {
            // When __builtin_clz(N) > 29, the loop below never runs, but because `adjacent` (below) is
            // set to 1 by default, the binary numbers b10 and b11 (2 and 3) think they are actually b110
            // and b111, so they count an extra adjacent bit.  To stop this, I'm just skipping them here.
            continue;
        }
        uint_fast8_t adjacent = 1; // Leftmost bit is 1, starting at 2nd from left
        uint_fast8_t bits = 0; // Number of adjacent bits in the target number N, determines magnitude
        uint32_t n = 30 - (uint32_t)__builtin_clz(N); // Bit index offset by -1 (rightmost bit is -1)

        // This is a funky equation.  It gets the sum of all adjacent bits where the number is lower than
        // the target number, from the closest log2 base (so if N = 420, this calculates the sum of all
        // adjacent bits from 0 to 255).  This is repeated in the following O(log(N)) loop.

        uint64_t summation = (uint64_t)n << n - 1; // Sum of all adjacent bits
        for (uint32_t i = n; i > 1; --i) { // Checking bits from left to right
            if ((uint32_t)(1 << i & N) == 0) {
                adjacent = 0; // Current bit is 0
                continue;
            }
            summation += ((uint64_t)i - 1 << i - 2) + (bits << i); // Modified calculation from above
            if (adjacent) {
                ++bits; // Count number of adjacent bits in the target number N
            }
            adjacent = 1; // Current bit is 1
        }

        // Special cases for the two rightmost bits to avoid negative rvalue bit shifts:

        switch (N & 3) {
        case 0:
            summation += bits; // b[]00
            break;
        case 1:
            summation += bits << 1; // b[]00 + b[]01
            break;
        case 2:
            summation += bits * 3 + adjacent; // b[]00 + b[]01 + b[]10
            break;
        default:
            summation += bits << 2 | adjacent << 1 | 1; // b[]00 + b[]01 + b[]10 + b[]11
        }

        // Check if my solution works:

        if (summation != sum) {
            printf("Found an error where N == %" SCNuFAST16 ", expected '%" SCNu64 "', got '%" SCNu64 "'\n", t, sum, summation);
            return EXIT_FAILURE; // Failure
        }
    }
    puts("100%, found no errors");
    return EXIT_SUCCESS; // Success
}

We can't share the test case, but for your submission your code printing

Case 5: 0 Case 6: 0

Where the correct output is 1, so there is a bug on your code

On Fri, 1 Mar 2024 at 14:40, Skeptx @.***> wrote:

https://lightoj.com/problem/fast-bit-calculations

I wrote a program in C to solve LOJ-1032 (Fast Bit Calculations). LOJ did not accept my full submission (test 1 passed, test 2 failed). I wrote a separate tool to verify my results, which seem to be accurate.

https://github.com/Skeptx/LightOJ-Problems/blob/main/Submissions/1032.c https://lightoj.com/submission/3087315 (compiled as C++ rather than C)

It passes the public test cases but fails the private ones. I'm not sure what's causing the issue because it's hidden. Verifying my results using the long method:

include #include #include #include

int main() { uint64_t sum = 0; for (uint32_t t = 0; t < 2147483648; ++t) { // For each input, from 0 to INT_MAX
  // Calculation to verify result:

  uint32_t N = t;
  uint32_t adj = 0; // Whether previous bit was 1 or 0
  while (N) {
      if (N & adj) { // Check if the previous rightmost bit and current rightmost bit were both set
          ++sum; // Add to number of adjacent bits
      }
      adj = N & 1; // Save whether or not the current rightmost bit is set
      N >>= 1; // Right shift and continue
  }

  // Simple % completion:

  if (t % 21474837 == 0) {
      printf("%d%%\n", t / 21474837);
  }

  // Start of the calculation I used for LightOJ:

  N = t;
  if (t < 4) {
      // When __builtin_clz(N) > 29, the loop below never runs, but because `adjacent` (below) is
      // set to 1 by default, the binary numbers b10 and b11 (2 and 3) think they are actually b110
      // and b111, so they count an extra adjacent bit.  To stop this, I'm just skipping them here.
      continue;
  }
  uint_fast8_t adjacent = 1; // Leftmost bit is 1, starting at 2nd from left
  uint_fast8_t bits = 0; // Number of adjacent bits in the target number N, determines magnitude
  uint32_t n = 30 - (uint32_t)__builtin_clz(N); // Bit index offset by -1 (rightmost bit is -1)

  // This is a funky equation.  It gets the sum of all adjacent bits where the number is lower than
  // the target number, from the closest log2 base (so if N = 420, this calculates the sum of all
  // adjacent bits from 0 to 255).  This is repeated in the following O(log(N)) loop.

  uint64_t summation = (uint64_t)n << n - 1; // Sum of all adjacent bits
  for (uint32_t i = n; i > 1; --i) { // Checking bits from left to right
      if ((uint32_t)(1 << i & N) == 0) {
          adjacent = 0; // Current bit is 0
          continue;
      }
      summation += ((uint64_t)i - 1 << i - 2) + (bits << i); // Modified calculation from above
      if (adjacent) {
          ++bits; // Count number of adjacent bits in the target number N
      }
      adjacent = 1; // Current bit is 1
  }

  // Special cases for the two rightmost bits to avoid negative rvalue bit shifts:

  switch (N & 3) {
  case 0:
      summation += bits; // b[]00
      break;
  case 1:
      summation += bits << 1; // b[]00 + b[]01
      break;
  case 2:
      summation += bits * 3 + adjacent; // b[]00 + b[]01 + b[]10
      break;
  default:
      summation += bits << 2 | adjacent << 1 | 1; // b[]00 + b[]01 + b[]10 + b[]11
  }

  // Check if my solution works:

  if (summation != sum) {
      printf("Found an error where N == %" SCNuFAST16 ", expected '%" SCNu64 "', got '%" SCNu64 "'\n", t, sum, summation);
      return EXIT_FAILURE; // Failure
  }
} puts("100%, found no errors"); return EXIT_SUCCESS; // Success }

— Reply to this email directly, view it on GitHub https://github.com/lightoj-dev/bugs-and-features/issues/216, or unsubscribe https://github.com/notifications/unsubscribe-auth/AALSTAO45DFQP432H2X4ENDYWCHNJAVCNFSM6AAAAABEB3XS7SVHI2DSMVQWIX3LMV43ASLTON2WKOZSGE3DGNJVGQ2TANY . You are receiving this because you are subscribed to this thread.Message ID: @.***>

Regards, Ahmad Faiyaz

lightoj-dev / bugs-and-features

Test case issue [Fast Bit Calculations] #216

include #include #include #include