I solved it without dp.

The solution is actually really easy when not dp. It is just the count of numbers that are divisible by (1ll<<i) and only by (1ll<<i) times 2(i-1). If you just draw 1-15 tree and try to solve for 1 15 you'll observe it. You just have to make these checks (i'm too lazy to explain it, but if you want just comment):

for (int i = 30; i >= 1; i--) {

int powerOf2 = 1ll << i;

int ci = countMultiples(n, m, powerOf2);

ci -= al;

int r = m / powerOf2;

int l = n / powerOf2;

an += 2 * (i - 1) * ci;

if (m % powerOf2 == 0 && (r % 2 != 0 || r == 0) && ci > 0) {// <-- These are the checks

an -= (i - 1);

}

if (n % powerOf2 == 0 && (l % 2 != 0 || l == 0) && ci > 0) {

an -= (i - 1);

}

al += ci;

}