Rewriting for loop efficiently, C

Question

I want to use a byte variable i to execute a bit of code 256 times. The line below loops indefinitely, is there a tidy alternative that would work?

for (i = 0; i < 255; i++){

Hopefully without using:

a 16 bit variable, (or any extra bits at all)
nested loops
while(1)
break; statements

Thanks

@Jodes: is `i` is unsigned 8bit, its max value is 255. The above will not go in an infinite loop. (But it will only loop 255 times). — Mat, Jun 26 '11 at 16:35
Maybe it's an oddity with my compiler then. I'm compiling for the PIC micro 16f with SourceBoost's BoostC — Jodes, Jun 26 '11 at 16:36
-1 for insisting on doing something stupid (using a byte variable) when there's an obvious solution (using the correct type, `int`). — R.. GitHub STOP HELPING ICE, Jun 26 '11 at 17:16
@Jodes: If you have unusual requirements because you're using an unusual platform, I'd suggest drawing attention to it in the question. All these people who are saying "just use an `int`" might have paused for thought if it had been clear from the start that you were building for an 8-bit microcontroller (where I can well believe that you might get smaller/faster code by using an 8-bit type)... — Matthew Slattery, Jun 26 '11 at 19:26

score 10 · Accepted Answer · answered Jun 26 '11 at 16:42

10

i = 0;
do {
  f(i);
} while(i++!=255);

answered Jun 26 '11 at 16:42

Timo

5,125
3
23
29

score 5 · Answer 2 · answered Jun 26 '11 at 16:36

5

Could always do this:

for (i = 0; i != 255; ++i)
{
    f(i);
}
f(255);

Honestly though, you'd be best just using an int. It's not going to be faster if you use an 8-bit integer. It's going to be in a register anyway.

answered Jun 26 '11 at 16:36

Peter Alexander

53,344
14
119
168

2

+1. If you really want to do this and must avoid a bigger datatype for the index. – Skurmedel Jun 26 '11 at 16:39
What if the target machine has a 4-bits processor? – Jun 26 '11 at 16:45
1

The C language requires `int` to have a range of at least 16 bits. – R.. GitHub STOP HELPING ICE Jun 26 '11 at 17:15
1

@WTP What if the target machine is an abacus? – David Heffernan Jun 26 '11 at 18:17
1

@WTP An Abacus Computer is Turing complete. – David Heffernan Jun 26 '11 at 18:25

score 3 · Answer 3 · answered Jun 26 '11 at 16:39

3

uint8_t i = 0;
do {
    ...
} while ((++i) != 0);

Of course the assumption is that i will overflow. That's not guaranteed by C standard, yet almost always happen when the compiler does not optimize too heavily.

answered Jun 26 '11 at 16:39

liori

40,917
13
78
105

Nice solution! Much better than mine :/ +1 – Ryan Amos Jun 26 '11 at 16:41
2

arithmetic with unsigned types is very well defined by the standard: it works `modulus (MAX_FOR_TYPE + 1)`. Your solution works as is. – pmg Jun 26 '11 at 16:51
@pmg, Ha, yes, I checked now. I thought this restriction applies to both unsigned and signed math. Thanks for comment! – liori Jul 01 '11 at 18:17

Ryan Amos · Answer 4 · 2011-06-27T12:24:49.680

1

The only way I can think of would be to have a boolean

b = 1;
for(i = 0; i != 0 || b; i++)
{
    b = 0;
    ...
}

Or you could use a short instead, which is 2x the size of a byte.

What's happening is that the maximum unsigned byte value is 255. I'm not sure what happens with unsigned bytes, but signed bytes become negative when you overflow.

edited Jun 27 '11 at 12:24

answered Jun 26 '11 at 16:36

Ryan Amos

5,422
4
36
56

score 1 · Answer 5 · edited May 23 '17 at 11:59

I would say unrolling the loop would be the most obvious way out of this one:

uint8_t i = 0;
for ( i = 0; i < 32; i++ )
{
    printf("Instance of loop %d\n", (8*i)+0);
    printf("Instance of loop %d\n", (8*i)+1);
    printf("Instance of loop %d\n", (8*i)+2);
    printf("Instance of loop %d\n", (8*i)+3);
    printf("Instance of loop %d\n", (8*i)+4);
    printf("Instance of loop %d\n", (8*i)+5);
    printf("Instance of loop %d\n", (8*i)+6);
    printf("Instance of loop %d\n", (8*i)+7);
}

In theory, this should also be quicker, since you have fewer tests and jumps. You could unroll more severely than this too, if needed.

You may also be interested in Duff's device (SO question explaining it), which would allow you to unroll any sized loop, not just one with nice factors. There are of course limits as it requires you store in memory the count of what you need, which in this case exceeds the 8-bit field, but, for the purposes of looping, say 137 times, it would come in useful.

Note you don't need to do the 8*i+1 stages, that's just to verify that enough events have happened.

Another note: "but I don't want to write my code 8 times!" can be overcome with the use of inline functions (C99) or macros (C89) as necessary.

Since the OP seems concerned with micro-optimization, you might be able to change the loop to `+= 8` and avoid 8 multiplies. — Chris Lutz, Jun 26 '11 at 19:55
@Chris the problem with += 8 is that the last iteration falls on 256 which you can't represent with a `uint8_t`. You'd have to start using two variables (one to count, one to increment by 8 to avoid multiplication) - it depends on which costs most at that stage. I'm slightly assuming the OP doesn't actually need to know the loop number, but rather just execute the code 256 times. — , Jun 26 '11 at 20:01

score 1 · Answer 6 · answered Jun 26 '11 at 19:15

1

If "byte" is char it will always be <255 on systems where char is signed (and 8 bits). If you must use a "byte" type, try unsigned char, which should work for your loop.

If it is not just an experiment, use int instead.

answered Jun 26 '11 at 19:15

Bo Persson

90,663
31
146
203

ShinTakezou · Answer 7 · 2011-06-26T16:41:33.597

0

EDIT: I get it wrong, it loops 255 times... :) A do-while construct is better:

  i = 0;
  do {
     // act
     i++;
  } while(i > 0);

The following two snippets loop 255 times, from 1 to 255.

  for(i = 1; i <= 255 && i != 0; i++)

should go. Or maybe

   for(i = 1; i > 0; i++)

edited Jun 26 '11 at 16:41

answered Jun 26 '11 at 16:34

ShinTakezou

9,432
1
29
39

But yes of course David Heffernan is right: on modern systems it is more natural for cpus to handle "int" rather than "char". – ShinTakezou Jun 26 '11 at 16:38
We're not supposed to use char or int or short or any of that. Just byte. – Ryan Amos Jun 26 '11 at 16:40
C has no byte, just char (char == byte likely); I've fixed the ans, since the old one looped 255 times (1-255); of course i *must* be unsigned char, otherwise this will loop a lot longer – ShinTakezou Jun 26 '11 at 16:43
Ah, I'm a Java noob, so I wouldn't know. I've only looked at C and done some C++ – Ryan Amos Jun 26 '11 at 16:50
in the second and third solution, it is enough you add a loner iteration before entering the loop, as suggested in another solution: `f(0); /* for loops with f(i) body */`. – ShinTakezou Jun 26 '11 at 16:50
ehm this evening it's not for me... "a lot longer" should be "a lot shorter" (i.e. half) since if i is signed, 127+1 is -1 and i > 0 is false, so it will stop far befor 256 iterations – ShinTakezou Jun 26 '11 at 16:52
already said? I am doing a lot of error sorry: 127+1 is not -1, but -128 of course (since -1 is 255, so to say) ... ok better I stop to answer questions so swiftly – ShinTakezou Jun 26 '11 at 17:01

score 0 · Answer 8 · answered Jun 26 '11 at 16:34

0

It will in general be quickest to declare i as an int. I can't imagine why you want to loop with an 8 bit integer. Perhaps you think it will be quicker than int but it won't.

answered Jun 26 '11 at 16:34

David Heffernan

601,492
42
1,072
1,490

Rewriting for loop efficiently, C

8 Answers8