By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,132 Members | 1,265 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,132 IT Pros & Developers. It's quick & easy.

A simple bit operation query

P: n/a
sfs
Hi All,

I have a number and I want to find the closest number multiple of 8
equal to or greater than n. ie. if n = 25 it should be 32. If n is 42
it should give me 42. (Basically 8 * (n/8)). But, I have to use bitwise
operators.

Can anyone suggest what can be done?

Regads,
Subhransu

Dec 27 '06 #1
Share this Question
Share on Google+
10 Replies


P: n/a
sfs said:
Hi All,

I have a number and I want to find the closest number multiple of 8
equal to or greater than n. ie. if n = 25 it should be 32. If n is 42
it should give me 42.
42 isn't a multiple of 8.
(Basically 8 * (n/8)). But, I have to use bitwise
operators.

Can anyone suggest what can be done?
If 8 * (n / 8) is all you want, it's easy enough: n &= ~7;

But I think you actually want ((n + 7) / 8) * 8, which is a bit trickier.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Dec 27 '06 #2

P: n/a
sfs wrote:
Hi All,

I have a number and I want to find the closest number multiple of 8
equal to or greater than n. ie. if n = 25 it should be 32. If n is 42
it should give me 42. (Basically 8 * (n/8)). But, I have to use bitwise
operators.

Can anyone suggest what can be done?

Going by your example and description, you mean, 8 * (n/8) + 8

8 = "1000" when represented in binary. Any multiple of 8 will have
last three bits as zeros. So,

val = n & ~7;
if (val < n)
n += 8;

Should work.
>
Regads,
Subhransu
Dec 27 '06 #3

P: n/a
p_cricket_...@yahoo.co.in wrote:
sfs wrote:
Hi All,

I have a number and I want to find the closest number multiple of 8
equal to or greater than n. ie. if n = 25 it should be 32. If n is 42
it should give me 42. (Basically 8 * (n/8)). But, I have to use bitwise
operators.

Can anyone suggest what can be done?


Going by your example and description, you mean, 8 * (n/8) + 8
Oops .. the + 8 part is only if n is not already divisible by 8.
The code below works though. I hope you do not have
restrictions that "only" bitwise operators must be used.
>
8 = "1000" when represented in binary. Any multiple of 8 will have
last three bits as zeros. So,

val = n & ~7;
if (val < n)
n += 8;

Should work.

Regads,
Subhransu
Dec 27 '06 #4

P: n/a
sfs

sfs wrote:
Hi All,

I have a number and I want to find the closest number multiple of 8
equal to or greater than n. ie. if n = 25 it should be 32. If n is 42
it should give me 42. (Basically 8 * (n/8)). But, I have to use bitwise
operators.

Can anyone suggest what can be done?

Regads,
Subhransu

Sorry!!! about the problem being wrong. It's (n+7)/8*8 and for 42 it
should give 48.

Dec 27 '06 #5

P: n/a
Richard Heathfield writes:
>sfs said:
>I have a number and I want to find the closest number multiple of 8
equal to or greater than n. ie. if n = 25 it should be 32. (...)
(Basically 8 * (n/8)). But, I have to use bitwise operators.

Can anyone suggest what can be done?

If 8 * (n / 8) is all you want, it's easy enough: n &= ~7;
....if n is nonnegative. If it's negative and two's complement,
the result may or may not be what you intend.
But I think you actually want ((n + 7) / 8) * 8, which is a bit
trickier.
Or ((n + 4) / 8) * 8, since he said the "closest" multiple of 8.

Anyway, he could loop over the one bits (4?, 8, 16, 32...) until he
finds a zero bit. Then invert those bits.

--
Hallvard
Dec 27 '06 #6

P: n/a
On Wed, 27 Dec 2006 14:21:14 +0100, Hallvard B Furuseth
<h.**********@usit.uio.nowrote:
>Richard Heathfield writes:
>>sfs said:
>>I have a number and I want to find the closest number multiple of 8
equal to or greater than n. ie. if n = 25 it should be 32. (...)
(Basically 8 * (n/8)). But, I have to use bitwise operators.

Can anyone suggest what can be done?

If 8 * (n / 8) is all you want, it's easy enough: n &= ~7;

...if n is nonnegative. If it's negative and two's complement,
the result may or may not be what you intend.
>But I think you actually want ((n + 7) / 8) * 8, which is a bit
trickier.

Or ((n + 4) / 8) * 8, since he said the "closest" multiple of 8.
No, he said closest multiple equal or greater.
>
Anyway, he could loop over the one bits (4?, 8, 16, 32...) until he
finds a zero bit. Then invert those bits.
Which bits are "those"? If we ignore your 4 above and take 9 as our
input, the "16 bit" is the first zero. Inverting it produces 25.
Inverting both the "16 bit" and the "8 bit" produces 17. Inverting
all bits from the "16 bit" down to the "1 bit" produces 22. None of
these are a multiple of 8.
Remove del for email
Dec 27 '06 #7

P: n/a
Barry Schwarz <sc******@doezl.netwrote:
On Wed, 27 Dec 2006 14:21:14 +0100, Hallvard B Furuseth
<h.**********@usit.uio.nowrote:
Anyway, he could loop over the one bits (4?, 8, 16, 32...) until he
finds a zero bit. Then invert those bits.
Which bits are "those"? If we ignore your 4 above and take 9 as our
input, the "16 bit" is the first zero. Inverting it produces 25.
Inverting both the "16 bit" and the "8 bit" produces 17. Inverting
all bits from the "16 bit" down to the "1 bit" produces 22. None of
these are a multiple of 8.
Right. I think the intended solution was something along the lines of
(hoping OP has vacated as HW folks do):

unsigned int round_up(unsigned int num) {
unsigned int shifter = 8;
num &= ~7;
while(1) {
num ^= shifter;
if( num & shifter ) {
return num;
}
shifter <<= 1;
}
}

Of course, this ignores the case of all-bits-1 being passed, but
hopefully that's the only failing of the code.

(On second thought, it rounds up 8 to 16, and so on, which I don't
know is the desired behavior. If that's the case,

if( (num & 7) == 0 ) {
return num;
}

should do the trick.)

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
Dec 27 '06 #8

P: n/a
Barry Schwarz <sc******@doezl.netwrites:
>On Wed, 27 Dec 2006 14:21:14 +0100, Hallvard B Furuseth
<h.**********@usit.uio.nowrote:
>Or ((n + 4) / 8) * 8, since he said the "closest" multiple of 8.

No, he said closest multiple equal or greater.
Oh, right.
>Anyway, he could loop over the one bits (4?, 8, 16, 32...) until he
finds a zero bit. Then invert those bits.

Which bits are "those"? If we ignore your 4 above and take 9 as our
input, the "16 bit" is the first zero. Inverting it produces 25.
Er, yes. I meant after handling the three lower bits. And I didn't
post actual code since it looked like homework.

--
Hallvard
Dec 27 '06 #9

P: n/a
"sfs" <sy******@gmail.comwrote in message
news:11*********************@a3g2000cwd.googlegrou ps.com...
Hi All,

I have a number and I want to find the closest number multiple of 8
equal to or greater than n. ie. if n = 25 it should be 32. If n is 42
it should give me 42. (Basically 8 * (n/8)). But, I have to use bitwise
operators.

Can anyone suggest what can be done?

Regads,
Subhransu
I think what you need is the expression '(n+7)&~7'.
This will round up to the next multiple of 8.

Regards,
Dag
Dec 27 '06 #10

P: n/a
"sfs" <sy******@gmail.comwrites:
I have a number and I want to find the closest number multiple of 8
equal to or greater than n. ie. if n = 25 it should be 32. If n is 42
it should give me 42. (Basically 8 * (n/8)). But, I have to use bitwise
operators.
No, you don't *have* to use bitwise operators, unless you're using a
system that doesn't support multiplication and division.

Or unless it's a homework assignment, which seems far more likely.
Can anyone suggest what can be done?
Yes, do it yourself. If you run into trouble, talk to your
instructor.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Dec 28 '06 #11

This discussion thread is closed

Replies have been disabled for this discussion.