Binary Palindromes
National Olympiad — National round
Submission name: binpal.cpp
Problem summary
Count integers in the inclusive decimal interval [x,y] whose ordinary binary representation, without leading zeros, is a palindrome.
Input
x y in decimal.
Output
The count in decimal.
Constraints
0<x≤y<10^18.
Worked example
An independently prepared example for this explanation.
Input
1 10
Output
5
Solution analysis
- Compute F(t), the number of positive binary palindromes at most t.
- For each shorter bit length L, there are 2^(ceil(L/2)−1) choices for the first half.
- At t’s bit length, every smaller first half works; mirror t’s first half and add one if that palindrome is at most t. Return F(y)−F(x−1).
Why it works
A palindrome is uniquely determined by its leading half. The leading bit must be one. Numerical order among equal-length palindromes follows the order of those halves, proving the count.
Complexity: O(log y) time and O(1) space.
Watch out. Do not enumerate all numbers or all palindromes: the range reaches 10^18.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A palindrome is uniquely determined by its leading half. The leading bit must be one.
#include<iostream>
using namespace std;
long long F(long long x){
if(x<=0){
return 0;
}
int L=64-__builtin_clzll(x);
long long ans=0;
for(int l=1;l<L;l++){
ans+=1LL<<((l+1)/2-1);
}
int h=(L+1)/2;
long long a=x>>(L-h);
ans+=a-(1LL<<(h-1));
long long p=a,t=(L%2?a>>1:a);
while(t){
p=(p<<1)|(t&1);
t>>=1;
}
if(p<=x){
ans++;
}
return ans;
}
int main(){
long long x,y;
cin>>x>>y;
cout<<F(y)-F(x-1)<<'\n';
}