Ideone.com

download

copy

#include <iostream>
#include <math.h>
using namespace std;
 
//binary representation
void bin(unsigned n)
{
    for (
    	int i = floor(log2(n));
	    i >= 0;
	    --i)
        (n & (1<<i))? printf("1"): printf("0");
}
 
//outputs the next greater int to x with exactly one 0 in binary representation
int nextHigherOneZero(int x){
	printf("X: %i=",x);
	bin(x);
	unsigned int n=0;
	//x < (result) < (result with all bits set) < (1<<n)
	//=> (result) >= x+1
	//=> (result with all bits set) >= x+2
	//=> (1<<n) >= x+3
	while((1<<n)<= x+2 ) ++n; 
	printf(";\tn: %i; 2^n: %i=",n,1<<n);
	bin(1<<n);
	unsigned int m=0;
	//basically: as long as we can increase m, do so
	//but m needs to be at least 2 below n, or we would remove the most significant bit
	while((1<<n)-1-(1<<(m+1)) > x && m<n-2){
		++m;
	}
	printf(";\tm: %i",m);
	//--m; //since we are smaller than x when exiting the last while
	return (1<<n)-1-(1<<m);
	}
 
 
int main() {
	int r=0;
	for(int i = 1; i<100;++i){
		r=nextHigherOneZero(i);
		printf("\nX: %i=",i);
		bin(i);
		printf(";\tnextHigherOneZero(x):%i=",r);
		bin(r);
		printf("\n");
	}
	return 0;
}

Success #stdin #stdout 0s 3456KB

stdin

copy

Standard input is empty

stdout

copy

X: 1=1;	n: 2; 2^n: 4=100;	m: 0
X: 1=1;	nextHigherOneZero(x):2=10
X: 2=10;	n: 3; 2^n: 8=1000;	m: 1
X: 2=10;	nextHigherOneZero(x):5=101
X: 3=11;	n: 3; 2^n: 8=1000;	m: 1
X: 3=11;	nextHigherOneZero(x):5=101
X: 4=100;	n: 3; 2^n: 8=1000;	m: 1
X: 4=100;	nextHigherOneZero(x):5=101
X: 5=101;	n: 3; 2^n: 8=1000;	m: 0
X: 5=101;	nextHigherOneZero(x):6=110
X: 6=110;	n: 4; 2^n: 16=10000;	m: 2
X: 6=110;	nextHigherOneZero(x):11=1011
X: 7=111;	n: 4; 2^n: 16=10000;	m: 2
X: 7=111;	nextHigherOneZero(x):11=1011
X: 8=1000;	n: 4; 2^n: 16=10000;	m: 2
X: 8=1000;	nextHigherOneZero(x):11=1011
X: 9=1001;	n: 4; 2^n: 16=10000;	m: 2
X: 9=1001;	nextHigherOneZero(x):11=1011
X: 10=1010;	n: 4; 2^n: 16=10000;	m: 2
X: 10=1010;	nextHigherOneZero(x):11=1011
X: 11=1011;	n: 4; 2^n: 16=10000;	m: 1
X: 11=1011;	nextHigherOneZero(x):13=1101
X: 12=1100;	n: 4; 2^n: 16=10000;	m: 1
X: 12=1100;	nextHigherOneZero(x):13=1101
X: 13=1101;	n: 4; 2^n: 16=10000;	m: 0
X: 13=1101;	nextHigherOneZero(x):14=1110
X: 14=1110;	n: 5; 2^n: 32=100000;	m: 3
X: 14=1110;	nextHigherOneZero(x):23=10111
X: 15=1111;	n: 5; 2^n: 32=100000;	m: 3
X: 15=1111;	nextHigherOneZero(x):23=10111
X: 16=10000;	n: 5; 2^n: 32=100000;	m: 3
X: 16=10000;	nextHigherOneZero(x):23=10111
X: 17=10001;	n: 5; 2^n: 32=100000;	m: 3
X: 17=10001;	nextHigherOneZero(x):23=10111
X: 18=10010;	n: 5; 2^n: 32=100000;	m: 3
X: 18=10010;	nextHigherOneZero(x):23=10111
X: 19=10011;	n: 5; 2^n: 32=100000;	m: 3
X: 19=10011;	nextHigherOneZero(x):23=10111
X: 20=10100;	n: 5; 2^n: 32=100000;	m: 3
X: 20=10100;	nextHigherOneZero(x):23=10111
X: 21=10101;	n: 5; 2^n: 32=100000;	m: 3
X: 21=10101;	nextHigherOneZero(x):23=10111
X: 22=10110;	n: 5; 2^n: 32=100000;	m: 3
X: 22=10110;	nextHigherOneZero(x):23=10111
X: 23=10111;	n: 5; 2^n: 32=100000;	m: 2
X: 23=10111;	nextHigherOneZero(x):27=11011
X: 24=11000;	n: 5; 2^n: 32=100000;	m: 2
X: 24=11000;	nextHigherOneZero(x):27=11011
X: 25=11001;	n: 5; 2^n: 32=100000;	m: 2
X: 25=11001;	nextHigherOneZero(x):27=11011
X: 26=11010;	n: 5; 2^n: 32=100000;	m: 2
X: 26=11010;	nextHigherOneZero(x):27=11011
X: 27=11011;	n: 5; 2^n: 32=100000;	m: 1
X: 27=11011;	nextHigherOneZero(x):29=11101
X: 28=11100;	n: 5; 2^n: 32=100000;	m: 1
X: 28=11100;	nextHigherOneZero(x):29=11101
X: 29=11101;	n: 5; 2^n: 32=100000;	m: 0
X: 29=11101;	nextHigherOneZero(x):30=11110
X: 30=11110;	n: 6; 2^n: 64=1000000;	m: 4
X: 30=11110;	nextHigherOneZero(x):47=101111
X: 31=11111;	n: 6; 2^n: 64=1000000;	m: 4
X: 31=11111;	nextHigherOneZero(x):47=101111
X: 32=100000;	n: 6; 2^n: 64=1000000;	m: 4
X: 32=100000;	nextHigherOneZero(x):47=101111
X: 33=100001;	n: 6; 2^n: 64=1000000;	m: 4
X: 33=100001;	nextHigherOneZero(x):47=101111
X: 34=100010;	n: 6; 2^n: 64=1000000;	m: 4
X: 34=100010;	nextHigherOneZero(x):47=101111
X: 35=100011;	n: 6; 2^n: 64=1000000;	m: 4
X: 35=100011;	nextHigherOneZero(x):47=101111
X: 36=100100;	n: 6; 2^n: 64=1000000;	m: 4
X: 36=100100;	nextHigherOneZero(x):47=101111
X: 37=100101;	n: 6; 2^n: 64=1000000;	m: 4
X: 37=100101;	nextHigherOneZero(x):47=101111
X: 38=100110;	n: 6; 2^n: 64=1000000;	m: 4
X: 38=100110;	nextHigherOneZero(x):47=101111
X: 39=100111;	n: 6; 2^n: 64=1000000;	m: 4
X: 39=100111;	nextHigherOneZero(x):47=101111
X: 40=101000;	n: 6; 2^n: 64=1000000;	m: 4
X: 40=101000;	nextHigherOneZero(x):47=101111
X: 41=101001;	n: 6; 2^n: 64=1000000;	m: 4
X: 41=101001;	nextHigherOneZero(x):47=101111
X: 42=101010;	n: 6; 2^n: 64=1000000;	m: 4
X: 42=101010;	nextHigherOneZero(x):47=101111
X: 43=101011;	n: 6; 2^n: 64=1000000;	m: 4
X: 43=101011;	nextHigherOneZero(x):47=101111
X: 44=101100;	n: 6; 2^n: 64=1000000;	m: 4
X: 44=101100;	nextHigherOneZero(x):47=101111
X: 45=101101;	n: 6; 2^n: 64=1000000;	m: 4
X: 45=101101;	nextHigherOneZero(x):47=101111
X: 46=101110;	n: 6; 2^n: 64=1000000;	m: 4
X: 46=101110;	nextHigherOneZero(x):47=101111
X: 47=101111;	n: 6; 2^n: 64=1000000;	m: 3
X: 47=101111;	nextHigherOneZero(x):55=110111
X: 48=110000;	n: 6; 2^n: 64=1000000;	m: 3
X: 48=110000;	nextHigherOneZero(x):55=110111
X: 49=110001;	n: 6; 2^n: 64=1000000;	m: 3
X: 49=110001;	nextHigherOneZero(x):55=110111
X: 50=110010;	n: 6; 2^n: 64=1000000;	m: 3
X: 50=110010;	nextHigherOneZero(x):55=110111
X: 51=110011;	n: 6; 2^n: 64=1000000;	m: 3
X: 51=110011;	nextHigherOneZero(x):55=110111
X: 52=110100;	n: 6; 2^n: 64=1000000;	m: 3
X: 52=110100;	nextHigherOneZero(x):55=110111
X: 53=110101;	n: 6; 2^n: 64=1000000;	m: 3
X: 53=110101;	nextHigherOneZero(x):55=110111
X: 54=110110;	n: 6; 2^n: 64=1000000;	m: 3
X: 54=110110;	nextHigherOneZero(x):55=110111
X: 55=110111;	n: 6; 2^n: 64=1000000;	m: 2
X: 55=110111;	nextHigherOneZero(x):59=111011
X: 56=111000;	n: 6; 2^n: 64=1000000;	m: 2
X: 56=111000;	nextHigherOneZero(x):59=111011
X: 57=111001;	n: 6; 2^n: 64=1000000;	m: 2
X: 57=111001;	nextHigherOneZero(x):59=111011
X: 58=111010;	n: 6; 2^n: 64=1000000;	m: 2
X: 58=111010;	nextHigherOneZero(x):59=111011
X: 59=111011;	n: 6; 2^n: 64=1000000;	m: 1
X: 59=111011;	nextHigherOneZero(x):61=111101
X: 60=111100;	n: 6; 2^n: 64=1000000;	m: 1
X: 60=111100;	nextHigherOneZero(x):61=111101
X: 61=111101;	n: 6; 2^n: 64=1000000;	m: 0
X: 61=111101;	nextHigherOneZero(x):62=111110
X: 62=111110;	n: 7; 2^n: 128=10000000;	m: 5
X: 62=111110;	nextHigherOneZero(x):95=1011111
X: 63=111111;	n: 7; 2^n: 128=10000000;	m: 5
X: 63=111111;	nextHigherOneZero(x):95=1011111
X: 64=1000000;	n: 7; 2^n: 128=10000000;	m: 5
X: 64=1000000;	nextHigherOneZero(x):95=1011111
X: 65=1000001;	n: 7; 2^n: 128=10000000;	m: 5
X: 65=1000001;	nextHigherOneZero(x):95=1011111
X: 66=1000010;	n: 7; 2^n: 128=10000000;	m: 5
X: 66=1000010;	nextHigherOneZero(x):95=1011111
X: 67=1000011;	n: 7; 2^n: 128=10000000;	m: 5
X: 67=1000011;	nextHigherOneZero(x):95=1011111
X: 68=1000100;	n: 7; 2^n: 128=10000000;	m: 5
X: 68=1000100;	nextHigherOneZero(x):95=1011111
X: 69=1000101;	n: 7; 2^n: 128=10000000;	m: 5
X: 69=1000101;	nextHigherOneZero(x):95=1011111
X: 70=1000110;	n: 7; 2^n: 128=10000000;	m: 5
X: 70=1000110;	nextHigherOneZero(x):95=1011111
X: 71=1000111;	n: 7; 2^n: 128=10000000;	m: 5
X: 71=1000111;	nextHigherOneZero(x):95=1011111
X: 72=1001000;	n: 7; 2^n: 128=10000000;	m: 5
X: 72=1001000;	nextHigherOneZero(x):95=1011111
X: 73=1001001;	n: 7; 2^n: 128=10000000;	m: 5
X: 73=1001001;	nextHigherOneZero(x):95=1011111
X: 74=1001010;	n: 7; 2^n: 128=10000000;	m: 5
X: 74=1001010;	nextHigherOneZero(x):95=1011111
X: 75=1001011;	n: 7; 2^n: 128=10000000;	m: 5
X: 75=1001011;	nextHigherOneZero(x):95=1011111
X: 76=1001100;	n: 7; 2^n: 128=10000000;	m: 5
X: 76=1001100;	nextHigherOneZero(x):95=1011111
X: 77=1001101;	n: 7; 2^n: 128=10000000;	m: 5
X: 77=1001101;	nextHigherOneZero(x):95=1011111
X: 78=1001110;	n: 7; 2^n: 128=10000000;	m: 5
X: 78=1001110;	nextHigherOneZero(x):95=1011111
X: 79=1001111;	n: 7; 2^n: 128=10000000;	m: 5
X: 79=1001111;	nextHigherOneZero(x):95=1011111
X: 80=1010000;	n: 7; 2^n: 128=10000000;	m: 5
X: 80=1010000;	nextHigherOneZero(x):95=1011111
X: 81=1010001;	n: 7; 2^n: 128=10000000;	m: 5
X: 81=1010001;	nextHigherOneZero(x):95=1011111
X: 82=1010010;	n: 7; 2^n: 128=10000000;	m: 5
X: 82=1010010;	nextHigherOneZero(x):95=1011111
X: 83=1010011;	n: 7; 2^n: 128=10000000;	m: 5
X: 83=1010011;	nextHigherOneZero(x):95=1011111
X: 84=1010100;	n: 7; 2^n: 128=10000000;	m: 5
X: 84=1010100;	nextHigherOneZero(x):95=1011111
X: 85=1010101;	n: 7; 2^n: 128=10000000;	m: 5
X: 85=1010101;	nextHigherOneZero(x):95=1011111
X: 86=1010110;	n: 7; 2^n: 128=10000000;	m: 5
X: 86=1010110;	nextHigherOneZero(x):95=1011111
X: 87=1010111;	n: 7; 2^n: 128=10000000;	m: 5
X: 87=1010111;	nextHigherOneZero(x):95=1011111
X: 88=1011000;	n: 7; 2^n: 128=10000000;	m: 5
X: 88=1011000;	nextHigherOneZero(x):95=1011111
X: 89=1011001;	n: 7; 2^n: 128=10000000;	m: 5
X: 89=1011001;	nextHigherOneZero(x):95=1011111
X: 90=1011010;	n: 7; 2^n: 128=10000000;	m: 5
X: 90=1011010;	nextHigherOneZero(x):95=1011111
X: 91=1011011;	n: 7; 2^n: 128=10000000;	m: 5
X: 91=1011011;	nextHigherOneZero(x):95=1011111
X: 92=1011100;	n: 7; 2^n: 128=10000000;	m: 5
X: 92=1011100;	nextHigherOneZero(x):95=1011111
X: 93=1011101;	n: 7; 2^n: 128=10000000;	m: 5
X: 93=1011101;	nextHigherOneZero(x):95=1011111
X: 94=1011110;	n: 7; 2^n: 128=10000000;	m: 5
X: 94=1011110;	nextHigherOneZero(x):95=1011111
X: 95=1011111;	n: 7; 2^n: 128=10000000;	m: 4
X: 95=1011111;	nextHigherOneZero(x):111=1101111
X: 96=1100000;	n: 7; 2^n: 128=10000000;	m: 4
X: 96=1100000;	nextHigherOneZero(x):111=1101111
X: 97=1100001;	n: 7; 2^n: 128=10000000;	m: 4
X: 97=1100001;	nextHigherOneZero(x):111=1101111
X: 98=1100010;	n: 7; 2^n: 128=10000000;	m: 4
X: 98=1100010;	nextHigherOneZero(x):111=1101111
X: 99=1100011;	n: 7; 2^n: 128=10000000;	m: 4
X: 99=1100011;	nextHigherOneZero(x):111=1101111

Discover > Sphere Engine API

Discover > IDE Widget

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language