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

Question

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

Answer 1

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;

Answer 2

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

---

[Edit]

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;