Finding the sum of 2^x and all powers of 8 less than 2^x

Is there a more efficient way, without a loop for example, to find a the end value for n for a specific x?

#include <stdio.h>
int main(void) {
const int x = 13;
int n;
for (int c = 0, p = 0; p < x; ++p) {
n = c+(1<<p);
if (p%3 == 0)
c = n;
}
printf("%d\n", n);
}


The first few values of this function should be:

1
3
5
9
25
41
73
201
329
585
1609
2633
4681

• I'm having trouble transitioning from your title to your code. I think c is tracking the sum of all powers of 8 less than x. But you're asking for n. And you call this a function (of x?) but it doesn't take any arguments. Commented Jan 12, 2023 at 21:22
• @Teepeemm The x variable is the input, and the output is stored in n. The main function is just the entry point of a C program. Commented Jan 12, 2023 at 23:45

c should not exist, and calculating n before your p%3 check is not a good idea. Further, don't p%3 at all; instead, just increment p by 3 instead of 1.

In Python this would look like (verified)

x = 13
c = sum(1<<p for p in range(0, x, 3)) | 1<<x
print(c)
# 12873


In C, since you're using integer math, don't add: instead, use binary-or. I didn't compile this:

const int x = 13;
unsigned n = 1 << x;
for (int p = 0; p < n; p += 3)
n |= 1u << p;


A more exotic algorithm that completes in O(log(n)) instead of O(n) time is:

x = 13
power = 3
total = 1
limit = 1<<x

while total < limit:
total |= total << power
power <<= 1

total = (total & (limit-1)) | limit


But given that your problem scale is tiny, this is premature optimisation and I doubt that it would be worth it. At 64-bit integer sizes the difference will be imperceptible.

Speaking of 64 bits: depending on the size of your int, you can just pre-populate a constant integer and then mask it without a loop, as in

x = 13
limit = 1 << x
full64 = 0x9249_2492_4924_9249
print(full64 & (limit - 1) | limit)


In C, something like

const int x = 13;
const uint64_t limit = 1ull << x;
const uint64_t full = 0x9249249249249249;
const uint64_t n = full & (limit - 1) | limit;


or even, in octal,

const int x = 13;
const uint64_t limit = 1ull << x;
const uint64_t full = 01111111111111111111111;
const uint64_t n = full & (limit - 1) | limit;

• I actually meant sum of 2^x and all powers of 8 *less than* 2^x. Your provided code works for values where x is 1 more than a multiple of 3, but not for others. I have edited the question to include some sample output. Though it should be straightforward enough to add the correct value to the output of the optimized versions. Commented Jan 12, 2023 at 3:09
• It seems simply |ing your solution with (1 << x) does the trick and is much faster than the loop, so I am still marking your answer as accepted. Commented Jan 12, 2023 at 3:26
• Reinderien, Better to stay with unsigned math and of the same size: & ((1 << x) - 1) --> & (((uint64_t)1 << x) - 1). Of course makes no difference with x = 13, still good to avoid left-shift into the sign-bit for other x. Commented Jan 12, 2023 at 12:58
• Reinderien, try int x = 11; or 12. n = full & ((1 << x) - 1); does not appear to work to form 1609, 2633. Commented Jan 12, 2023 at 19:06
• That full constant 01111… can be generated by dividing 07777… by 7, so we can write template<std::unsigned_integral T> const T full = (~T{0} / 7) >> (sizeof (T) * CHAR_BIT % 3); (provided we comment it adequately!). Commented Jan 18, 2023 at 11:42

Is there a more efficient way, without a loop for example, to find a the end value for n for a specific x?

Yes.

#include <stdio.h>

// Finding the sum of 2^x and all powers of 8 less than 2^x
int main(void) {
const int x = 13 - 1;  // OP's x is off by 1.
unsigned power2 = 1u << x;
unsigned sum_power8 = 011111111111;
sum_power8 &= power2 - 1;
unsigned n = power2 + sum_power8;
printf("%u\n", n);
}


Ouptut

4681


Thought I'd try @Reinderien simplification.

#include <stdio.h>
#include <inttypes.h>

void foo(int x) {
int n;
for (int c = 0, p = 0; p < x; ++p) {
n = c + (1 << p);
if (p % 3 == 0)
c = n;
}
printf("%2d %12d %o\n", x, n, n);
}

void foo2(int x) {
const uint64_t full = 01111111111111111111111;
const uint64_t n = full & ((1llu << x) - 1);
printf("%2d %12" PRIu64 " %" PRIo64 "\n", x, n, n);
}

int main() {
for (int x = 0; x <= 13; x++) {
foo(x);
}
for (int x = 0; x <= 13; x++) {
foo2(x);
}
}


Yet came up with different results than OP's.

 0           10 12
1            1 1
2            3 3
3            5 5
4            9 11
5           25 31
6           41 51
7           73 111
8          201 311
9          329 511
10          585 1111
11         1609 3111
12         2633 5111
13         4681 11111
0            0 0
1            1 1
2            1 1
3            1 1
4            9 11
5            9 11
6            9 11
7           73 111
8           73 111
9           73 111
10          585 1111
11          585 1111
12          585 1111
13         4681 11111


Something is amiss.

• int n; should be int n = 0; in case loop never iterates. Even if the function is planned to be call only with x >= 1, good coding practice to avoid troubles of using uninitialized objects.

Candidate fix:

void foo3(int x) {
int n = 0;
int p = (x-1)/3*3;
const uint64_t full = 01111111111111111111111;
n = (int) (full & ((1llu << p) - 1));
int c = n;

// This portion likely can be further simplified.
for (; p  < x; p ++) {  // Loop 0,1,2 times
n = c + (1 << p);
if (p % 3 == 0)
c = n;
}
printf("%2d %12d %o\n", x, n, n);
}


Output

 0            0 0
1            1 1
2            3 3
3            5 5
4            9 11
5           25 31
6           41 51
7           73 111
8          201 311
9          329 511
10          585 1111
11         1609 3111
12         2633 5111
13         4681 11111


Instead of starting with OP's code, consider the goal:

sum of 2^x and all powers of 8 less than 2^x

A direct encoding of that is

void foo4(unsigned x) {
unsigned long long power2 = 1uLL << x;

unsigned long long sum_power8 = 0;
for (unsigned long long power8 = 1; power8 < power2; power8 *= 8) {
sum_power8 += power8;
}

unsigned long long n = power2 + sum_power8;
printf("%2u %12llu %llo\n", x, n, n);
}


With output:

0            1 1
1            3 3
2            5 5
3            9 11
4           25 31
5           41 51
6           73 111
7          201 311
...


This also shows that OP's x is off-by-one. With x=1, foo(x) is 3, not 1.

Simplified code:

void foo5(unsigned x) {
unsigned long long power2 = 1uLL << x;

unsigned long long sum_power8 = 01111111111111111111111;
sum_power8 &= power2 - 1;

unsigned long long n = power2 + sum_power8;
printf("%2u %12llu %llo\n", x, n, n);
}


Pedantically, unsigned long long sum_power8 = 01111111111111111111111; should be reworked to handle unsigned long long wider than 64-bit such as

// https://stackoverflow.com/a/4589384/2410359
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))
unsigned long long sum_power8 = (ULLONG_MAX/7 >> (IMAX_BITS(ULLONG_MAX)%3))*8 + 1;