Один из популярных подходов.
Представим, что вам дали задачу где происходят какие-то битовые операции.
Например вам дали натуральное число n (1 <= n <= 1e18) и вы должны посчитать сумму (i & j) по всем i, j (1 <= i, j <= n).

Давайте посмотрим на двоичное представление числа (i & j) - в этом представление может быть всего 60 битов. Это нам позволяет свести исходную задачу к другой задаче.
Пусть cnt[bit] это количество чисел x, таких, что (1 <= x <= n) и в двоичном представление числа x есть бит на позиции bit (иначе говоря (x » bit) & 1 == 1).
Тогда ответом на задачу была бы сумма 2^bit * cnt[bit]^2. (0 <= bit < 60).

Подход заключается в том чтобы отдельно рассмотреть каждый бит и после просуммировать.

Надеюсь такого рода задача позволит вам замечать, что иногда можно искать отдельно сумму по всем битам.

что касается cnt[bit] то ее можно посчитать с помощью digit dp