После того как решил, полез смотреть комментарии и понял, что, кажется, сделал не так как подразумевалось. Вместо побитовых операций, циклов и арифметики я перевёл Long в строку с помощью toBinaryString, затем убрал в ней все нули реплэйсом. Получилась строка единиц, длину которой я проверил на чётность. Вот сижу и не понимаю имеет право на жизнь мой вариант или в нём есть "неправильность", которую я не вижу. Ну и тест на скорость я пока не знаю как сделать.