5
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Teepeemm
    Jan 12, 2023 at 21:22
  • \$\begingroup\$ @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. \$\endgroup\$ Jan 12, 2023 at 23:45

2 Answers 2

4
\$\begingroup\$

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;
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 12, 2023 at 3:09
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 12, 2023 at 3:26
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jan 12, 2023 at 12:58
  • \$\begingroup\$ Reinderien, try int x = 11; or 12. n = full & ((1 << x) - 1); does not appear to work to form 1609, 2633. \$\endgroup\$ Jan 12, 2023 at 19:06
  • \$\begingroup\$ 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!). \$\endgroup\$ Jan 18, 2023 at 11:42
3
\$\begingroup\$

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;
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.