Medium
Branchy vs. branchless code on unpredictable data
arr[i]'s low bit is effectively random (no exploitable pattern) for every element. Version A uses a data-dependent branch; version B computes the same result with unconditional bitwise arithmetic every iteration (strictly more ALU ops, but no branch). For large, random input, which runs faster, and why?
main.cpp
// Version A: data-dependent branch
for (int i = 0; i < n; ++i) {
if (arr[i] & 1) sum += arr[i];
else sum -= arr[i];
}
// Version B: branchless
for (int i = 0; i < n; ++i) {
int mask = -(arr[i] & 1); // all-1s if odd, all-0s if even
sum += (arr[i] & mask) - (arr[i] & ~mask);
}25 of 47 in Computer Architecture