Anonymous
11/8/2025, 5:25:40 AM
No.107139726
>>107113592
>>107133556
Searches with popcnt check, around 32 bits, in random data, are getting wrecked by normal distribution. They keep entering the false positive branch.
Any ideas?
if (num_bits < 64) {
u32 bk = 0;
for (; bk < num_buckets - 1; ++bk) {
const auto left = BIT ? buckets[bk] : ~buckets[bk];
if (popcnt(left) >= num_bits) {
auto runs = left;
auto num_b = num_bits;
while (num_b > 1) {
const auto step = num_b >> 1;
runs &= runs >> step;
num_b -= step;
}
if (runs) return idx(bk, tzcnt(runs));
}
const auto right = BIT ? ~buckets[bk + 1] : buckets[bk + 1];
const auto ones_left = lzcnt(~left);
const auto ones_right = tzcnt(right);
if (ones_left + ones_right >= num_bits) return idx(bk, 64 - ones_left);
}
const auto last = BIT ? buckets[bk] : ~buckets[bk];
if (popcnt(last) >= num_bits) {
auto runs = last;
auto num_b = num_bits;
while (num_b > 1) {
const auto step = num_b >> 1;
runs &= runs >> step;
num_b -= step;
}
if (runs) return idx(bk, tzcnt(runs));
}
}
>>107133556
Searches with popcnt check, around 32 bits, in random data, are getting wrecked by normal distribution. They keep entering the false positive branch.
Any ideas?
if (num_bits < 64) {
u32 bk = 0;
for (; bk < num_buckets - 1; ++bk) {
const auto left = BIT ? buckets[bk] : ~buckets[bk];
if (popcnt(left) >= num_bits) {
auto runs = left;
auto num_b = num_bits;
while (num_b > 1) {
const auto step = num_b >> 1;
runs &= runs >> step;
num_b -= step;
}
if (runs) return idx(bk, tzcnt(runs));
}
const auto right = BIT ? ~buckets[bk + 1] : buckets[bk + 1];
const auto ones_left = lzcnt(~left);
const auto ones_right = tzcnt(right);
if (ones_left + ones_right >= num_bits) return idx(bk, 64 - ones_left);
}
const auto last = BIT ? buckets[bk] : ~buckets[bk];
if (popcnt(last) >= num_bits) {
auto runs = last;
auto num_b = num_bits;
while (num_b > 1) {
const auto step = num_b >> 1;
runs &= runs >> step;
num_b -= step;
}
if (runs) return idx(bk, tzcnt(runs));
}
}