A problem to solve..need help

[Witless]

This is 'supposed' to be a simple problem and shouldn't need too much
time to solve :S

Below is a function that works like this:

int fn(int input)
{

int x=(input/8);

if(x%2)
x= x*8 + 8;
else
x = x*8;

return x;

}

Input -> Output
===========
0..7 -> 0
8..15 -> 16
16..23 -> 16
24..31 -> 32
32..39 -> 32
40..47 -> 48
48..56 -> 48

Problem:
See if you can come up with a more efficient solution that can do it
without any division or multiplication operations.

Hint:
Think about what the numbers look like in binary.

If you have no time to look at it, let me know ASAP.

Thanks for your help in advance.

 

[Ben Pfaff]

int fn(int input)
{

int x=(input/8);

if(x%2)
x= x*8 + 8;
else
x = x*8;

return x;

}

Problem:
See if you can come up with a more efficient solution that can do it
without any division or multiplication operations.

If there is a more efficient solution, then your compiler will
probably come up with it automatically. (If it doesn't, change
the type of `input' to `unsigned' and try again.) It is a waste
of a programmer's time to try to optimize this code.

 

[Malcolm]

This is 'supposed' to be a simple problem and shouldn't need too much
time to solve :S

int fn(int input)
{

int x=(input/8);

if(x%2)
x= x*8 + 8;
else
x = x*8;

return x;

}

See if you can come up with a more efficient solution that can do it
without any division or multiplication operations.

Hint:
Think about what the numbers look like in binary.

I won't do your homework for you, but think how you would multiply a decimal
number by ten. How would you multiply by 100, or 1000?

As a further hint, make sure you know what the << and >> operators do in C,
also the logical operators (| & ^ and ~), and think about what a binary
number modulus a power of two looks like.

 

[Jack Klein]

This is 'supposed' to be a simple problem and shouldn't need too much
time to solve :S

Below is a function that works like this:

int fn(int input)
{

int x=(input/8);

if(x%2)
x= x*8 + 8;
else
x = x*8;

return x;

}

Input -> Output
===========
0..7 -> 0
8..15 -> 16
16..23 -> 16
24..31 -> 32
32..39 -> 32
40..47 -> 48
48..56 -> 48

Problem:
See if you can come up with a more efficient solution that can do it
without any division or multiplication operations.

Hint:
Think about what the numbers look like in binary.

If you have no time to look at it, let me know ASAP.

Thanks for your help in advance.

I agree with Ben, trying to optimize this with type int is rather
silly. What is it supposed to return if you pass it -1?

On the other hand, if you can deal with unsigned numbers, there is
this:

unsigned fn(unsigned int inp)
{
return (inp + 8) & ~(0xfU);
}

 

[Peter Nilsson]

This is 'supposed' to be a simple problem and shouldn't need too much
time to solve :S

Below is a function that works like this:

int fn(int input)
{

int x=(input/8);

if(x%2)
x= x*8 + 8;
else
x = x*8;

return x;

}

A compiler must preserve the literal semantics of signed division. Presumably, your
assignment must do the same.

Input -> Output
===========
0..7 -> 0
8..15 -> 16
16..23 -> 16
24..31 -> 32
32..39 -> 32
40..47 -> 48
48..56 -> 48

You haven't said whether this is the entire input range, or merely a sample. That would
dramatically effect the answer.

Problem:
See if you can come up with a more efficient solution that can do it
without any division or multiplication operations.

Chances are, the compiler already does that. Hence Ben's comments.

Hint:
Think about what the numbers look like in binary.

Which is fine if input is always non-negative. It's not so simple for negative input in
which case the value bits could be just about anything under C90. Even under C99 there are
three varieties of negative integer representations. Under C90 there are also two classes
of division when one of the operands is negative!

If you have no time to look at it, let me know ASAP.

[If we didn't have time to look at it, why would we have the time to let you know ASAP
(sic)?]

The nearest ISO C solution I can think of is...

#include <limits.h>

int fn(int input)
{
if (input >= 0)
return input - (input & 7) + (input & 8);

if (INT_MIN + 1 == -INT_MAX && input == INT_MIN)
return INT_MIN;

if (-7 / 8 < 0)
{
input = -1-input;
return -input + (input & 7) - (input & 8);
}

return input + (-input & 15);
}

This still has a compile time test for the class of division which a C90 implementation
might use. I can't see a way around that without using / or %. Note that it's not obvious
that this is a more efficient solution!

Of course, if you make the input an unsigned int, the solution is trivial as Jack has
mentioned.

 

[RoSsIaCrIiLoIA]

This is 'supposed' to be a simple problem and shouldn't need too much
time to solve :S

Below is a function that works like this:

int fn(int input)
{

int x=(input/8);

if(x%2)
x= x*8 + 8;
else
x = x*8;

return x;

}

Input -> Output
===========
0..7 -> 0
8..15 -> 16
16..23 -> 16
24..31 -> 32
32..39 -> 32
40..47 -> 48
48..56 -> 48

Problem:
See if you can come up with a more efficient solution that can do it
without any division or multiplication operations.

Hint:
Think about what the numbers look like in binary.

If you have no time to look at it, let me know ASAP.

Thanks for your help in advance.

int fn(int a)
{if (0<=a && a<=7) return 0;
else if(8<=a && a<=23) return 16;
else if(24<=a && a<=39) return 32;
else return 48;
}