yukicoder No.638 Sum of "not power of 2"

問題はこちら
No.638 Sum of "not power of 2" - yukicoder

考察により、答えは次のようになることがわかる
・Nが1,2,3,4,5,7のとき-1
・N-3が2ベキでないときa=3,b=N-3
・N-5が2ベキでないときa=5,b=N-5
正当性を示す。
2ベキでない最小の数は3、2番目に小さい数は5なので、1,2,3,4,5,7がダメなのは明らか。
よって「N≠1,2,3,4,5,7のとき、N-3とN-5がともに2ベキになることはない」を示せば良い。
差が2であるような2ベキの組は2,4しかなく、N≧8よりN-5＞2、N-3＞4であるから、これに該当することはない。

N-3が2ベキであるかどうかはpopcntが1であるかどうかを見れば良い

main(){
	long n;
	scanf("%ld",&n);
	if(n<=5||n==7)puts("-1");
	else if(__builtin_popcountl(n-3)!=1)printf("3 %ld",n-3);
	else printf("5 %ld",n-5);
}

ところで、popcntを自前で実装するときの有名テクとして次のようなものがある

int popcnt(int n){
	int count=0;
	while(n){
		count++;
		n&=n–1;
	}
	return count;
}

実はn&n-1により、nにおいて1になっている一番下のbitを消すことができる。
ということでpopcntを使わなくても、n-3&((n-3)-1)が0かどうかを見れば良いことが分かる。

long n;
main(m){
	scanf("%ld",&n);
	m=n-3&n-4?3:5;
	printf(n>5&&n-7?"%d %ld":"-1",m,n-m);
}

83B