in reply to Detecting whether UV fits into an NV


I poked around with it and came up with something for you to figure it out without the looping.

$ cat // funky_bits.cpp // // experiment with odd bit handling? // // 20200227 #include <stdio.h> // Some test cases unsigned long long foo[] = { 0xcab312, 0xdeadbeef, 0xdeadbeef0, 0xdeadbeef000, 0x138, 9007199254740992ULL, 18446744073709551615ULL }; // Needs a good name, and the type shenanigans should be cleaned up bool duzzit_fit(unsigned long long t) { // First we need to identify the lowest bit set long long neg_t = -(long long)t; long long last_set = t & neg_t; // Shift it left 52 bits to get location of lowest invalid bit // NOTE: If smallest invalid bit is far enough left, then this wil +l turn into 0 // making the invalid bits also 0, which happens to be OK! long long smallest_invalid = last_set << 52; // Convert it to a bit mask for the smallest invalid bit and those + to the left. unsigned long long valid_bits = smallest_invalid - 1; unsigned long long invalid_bits = ~valid_bits; // Uncomment for debugging //printf( " t:%16llx\n" // " last_set:%16llx\n" // " neg_t:%16llx\n" // "smallest_invalid:%16llx\n" // " valid_bits:%16llx\n" // " invalid_bits:%16llx\n", // t, last_set, neg_t, smallest_invalid, // valid_bits, invalid_bits); // It's a 'valid' number unless one of the upper-order invalid bit +s are set return ! (t & invalid_bits); } int main(int, char **) { for (int z=0; z<sizeof(foo)/sizeof(foo[0]); ++z) { unsigned long long i = foo[z]; bool b = duzzit_fit(i); printf("%lld: %s\n", i, b ? "OK" : "**NOPE**"); } return 0; } $ clang -o funky_bits $ ./funky_bits 13284114: OK 3735928559: OK 59774856944: OK 15302363377664: OK 312: OK 9007199254740992: OK -1: **NOPE**

Cleaning it up, adding more test cases, further testing, debugging and simplification are all left as exercises for the reader... ;^D

I was originally thinking of making a lookup table, but thought of this along the way.

Update: fixed the abomination that was the first sentence.


When your only tool is a hammer, all problems look like your thumb.