Ну и окей, нам то че с того? Вот мы с вами когда пользуемся операторами +,-,*,/ - никогда не паримся, просто держим в голове что если числа с которыми мы делаем вычисления будут слишком большими - надо будет или делать до вычисления какую-нибудь проверку, или работать с long/BigInteger, или с Math.addExact(), тут джекичанских путей решения этой задачи хватает. В чем тогда бага этой строки?
val = val | (1 << j);

Если представить это выражение чисто в виде используемых типов - проблема станет очевиднее (нет):
long = long | (int << int);
Целевой тип с которым мы работаем - long. А в части (1 << j) - мы получаем результат int, который воткнется в проблему переполнения раньше чем long. Поэтому что бы поправить ошибку - в коде надо явно указать что побитовый сдвиг мы делаем для long:
val = val | (1L << j);

Похожая ошибка на более простом кейсе - как если написать код:

int a = ...; //любое значение
long result = 2 * a; //результат умножения - int

И расстраиваться почему это у нас для больших чисел некорректно идет умножение. Фикс:
long result = 2L * a; //результат умножения - long

Выводы. Их несколько.

- Математика, типы, циклы и условия - только и ждут чтобы поиметь вас, поэтому знайте врага в лицо и будьте бдительны:)
- Баги встречаются везде, даже в крупнейших проектах. Тесты и автотесты - самое годное оружие против них. Напиши автотест - сделай мир лучше!