Skip to main content
Code Golf

Return to Answer

Removed 1 byte by changing `++t<=` to `t++<`
Source Link
Chris
Chris
  • 2k
  • 12
  • 26

C, 139 137137 136 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;++t<=r3<<2*a;y*=2;t++<r?y++,r-=t++:t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}

C, 139 137 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;++t<=r?y++,r-=t++:t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}

C, 139 137 136 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;t++<r?y++,r-=t++:t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}
added 9 characters in body
Source Link
Chris
Chris
  • 2k
  • 12
  • 26

C, 139139 137 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;++t<=r?y++,r-=(t++)=t++:t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}

C, 139 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;++t<=r?y++,r-=(t++):t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}

C, 139 137 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;++t<=r?y++,r-=t++:t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}
added 36 characters in body
Source Link
Chris
Chris
  • 2k
  • 12
  • 26

C, 139 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;++t<=r?y++,r-=(t++):t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}

C, 139 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;++t<=r?y++,r-=(t++):t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}

C, 139 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;++t<=r?y++,r-=(t++):t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}
added 43 characters in body
Source Link
Chris
Chris
  • 2k
  • 12
  • 26
Source Link
Chris
Chris
  • 2k
  • 12
  • 26