Bitwise operators

[Santhosh]

Hi to all,
How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?

If we have n = 34

Result has to be 3,4.

Thanks a billion for your reply in advance.

[Walter Roberson]

In article <39**********************************@p39g2000prm. googlegroups.com>,
Santhosh <sa****************@gmail.comwrote:

>How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?

If we have n = 34

>Result has to be 3,4.

This is obviously an artificial question such as for a homework
assignment or an interview question, so I decline to demonstrate.

I would recommend, though, being more explicit as to which
are the "bitwise operators" that are to be considered. For example
would a solution be ruled out if it had loops or conditional
tests? Is comparision to 0 a bitwise operation ?
--
"There is no greater calling than to serve your fellow men.
There is no greater contribution than to help the weak.
There is no greater satisfaction than to have done it well."
-- Walter Reuther

[=?ISO-8859-1?Q?Tom=E1s_=D3_h=C9ilidhe?=]

On Jun 18, 10:32*pm, Santhosh <[e-mail]:

*If we have n *= 34

Result has to be 3,4

Ever heard of mathematics? Number systems?

A typical number system consists of:
1) Radix = the amount of different symbols
2) The actual pictures that represent the symbols

Let's take the "octal" number system:
1) Radix = 8
2) Symbols = 0 1 2 3 4 5 6 7

If you want to represent a number that is greater than or equal to
radix, then you need more than one digit. So in octal, the number
eight is written as:
10
And nine is written as:
11

Here, the "11" is equal to:
1 multiplied by (8 to the power of 1)
+1 multiplied by (8 to the power of 0)

Try another octal number: 2763
2 multiplied by (8 to the power of 3)
+7 multiplied by (8 to the power of 2)
+6 multiplied by (8 to the power of 1)
+3 multiplied by (8 to the power of 0)

Try think now, if you had a number in decimal such as 34, then what
would you do to it to get the first digit and the second digit? I'll
give you a clue, it involves using the radix, i.e. 10, in conjunction
with a mathematical operation such as division.

[Peter Nilsson]

Santhosh wrote:

Hi to all,
How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?

Yes, but that isn't a question about C, merely a question on
algorithms. Google for BCD.

--
Peter

[Walter Roberson]

In article <01**********************************@w34g2000prm. googlegroups.com>,
Peter Nilsson <ai***@acay.com.auwrote:

>Santhosh wrote:

>How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?

>Yes, but that isn't a question about C, merely a question on
algorithms. Google for BCD.

In a way, it is a question about C, as "bitwise operators" would
have to be interpreted in the context of C: the exact operators
which are considered "bitwise" operators will make a difference
to whether such an algorithm can be constructed.

Turing equivilence only works for "sufficiently powerful"
computation systems, and the four operators ~ ^ & | alone
are not "sufficiently powerful" for to be able to generate
any arbitrary algorithm.
--
"History is a pile of debris" -- Laurie Anderson

[Antoninus Twink]

On 18 Jun 2008 at 22:09, Walter Roberson wrote:

Turing equivilence only works for "sufficiently powerful" computation
systems, and the four operators ~ ^ & | alone are not "sufficiently
powerful" for to be able to generate any arbitrary algorithm.

They are sufficiently powerful to generate all the operations performed
by your favorite ALU.

[Richard Heathfield]

Walter Roberson said:

<snip>

Turing equivilence only works for "sufficiently powerful"
computation systems, and the four operators ~ ^ & | alone
are not "sufficiently powerful" for to be able to generate
any arbitrary algorithm.

Well, I agree that you need a "jump operator" of some kind, and a "test
operator". But it's amazing what you /can/ do with the ~ ^ & | ><<
collection (you missed the shifts, which is presumably just an oversight).
^ gives you a half-adder. & and << give you the other half, handing you
full addition on a plate. Using two's complement gives you subtraction
almost for free. With those, you can do multiplication, division, and mod.
And with those five arithmetic operators in place, you can do just about
anything that can be done.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Johannes Bauer]

Richard Heathfield schrieb:

Well, I agree that you need a "jump operator" of some kind, and a "test
operator".

Not for this problem. The data type which is input has a finite size,
therefore enumeration is possible, yielding an extremely huge and
complex boolean expression that does not need one single jump or test.
Probably far too huge to be compiled by any compiler, but, hey...

Regards,
Johannes

--
"Wer etwas kritisiert muss es noch lange nicht selber besser können. Es
reicht zu wissen, daß andere es besser können und andere es auch
besser machen um einen Vergleich zu bringen." - Wolfgang Gerber
in de.sci.electronics <47***********************@news.freenet.de>

[Johannes Bauer]

Johannes Bauer schrieb:

Richard Heathfield schrieb:

>Well, I agree that you need a "jump operator" of some kind, and a
"test operator".

Not for this problem. The data type which is input has a finite size,
therefore enumeration is possible, yielding an extremely huge and
complex boolean expression that does not need one single jump or test.
Probably far too huge to be compiled by any compiler, but, hey...

For demonstration purposes, I've created a program which enumerates the
numbers from 0-99 and always does output the 10^1 digit:

http://nopaste.org/p/ajyaa3Ipe

It's mighty impressive ;-)

Regards,
Johannes

--
"Wer etwas kritisiert muss es noch lange nicht selber besser können. Es
reicht zu wissen, daß andere es besser können und andere es auch
besser machen um einen Vergleich zu bringen." - Wolfgang Gerber
in de.sci.electronics <47***********************@news.freenet.de>

[Richard Heathfield]

Johannes Bauer said:

Richard Heathfield schrieb:

>Well, I agree that you need a "jump operator" of some kind, and a "test
operator".

Not for this problem.

Quite. My comment was made with regard to Walter's more general claim that
"the four operators ~ ^ & | alone are not "sufficiently powerful" for to
be able to generate any arbitrary algorithm".

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Walter Roberson]

In article <n9************@joeserver.homelan.net>,
Johannes Bauer <df***********@gmx.dewrote:

>For demonstration purposes, I've created a program which enumerates the
numbers from 0-99 and always does output the 10^1 digit:

(using bitwise operators)

>http://nopaste.org/p/ajyaa3Ipe

>It's mighty impressive ;-)

Definitely a labour of love!
--
"When a scientist is ahead of his times, it is often through
misunderstanding of current, rather than intuition of future truth.
In science there is never any error so gross that it won't one day,
from some perspective, appear prophetic." -- Jean Rostand

[onkar.n.mahajan]

On Jun 19, 2:32 am, Santhosh <[e-mail]:

Hi to all,
How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?

If we have n = 34

Result has to be 3,4.

Thanks a billion for your reply in advance.

Indians always ask interview Questions ! :-)

[onkar.n.mahajan]

On Jun 19, 2:32 am, Santhosh <[e-mail]:

Hi to all,
How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?

If we have n = 34

Result has to be 3,4.

Thanks a billion for your reply in advance.

This is a comp.lang.c forum - "not to discuss interview Qs related to
algos here" , we are here to discuss Qs related to C programming
language !

[santosh]

on*************@gmail.com wrote:

On Jun 19, 2:32 am, Santhosh <[e-mail]:

>Hi to all,
How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?

If we have n = 34

Result has to be 3,4.

Thanks a billion for your reply in advance.

This is a comp.lang.c forum - "not to discuss interview Qs related to
algos here" , we are here to discuss Qs related to C programming
language !

No, the question is perfectly legitimate[1]. That it may be
an "interview question" or a homework question is irrelevant. Of course
questions of this type often don't elicit the type of response that the
OP would like, but that's a different matter.

1. Always assuming that the OP wants a C based answer. Otherwise it's
not topical here and he should probably post to comp.programming.

[rahul]

On Jun 19, 2:32 am, Santhosh <[e-mail]:

Hi to all,
How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?

If we have n = 34

Result has to be 3,4.

Thanks a billion for your reply in advance.

We generally use % and / to get the individual digits.
#include <stdio.h>
#include <stdlib.h>

int
main(void) {
int num = 34;
int digit = 0;
while (num != 0) {
digit = num % 10;
num /= 10;
printf("%d\n", digit);
}
return 0;
}

The result will be 4, 3 as it starts separating from the unit's place.
You are not clear on where do you want to use the bitwise operator.

[den2k]

On 19 Giu, 08:35, rahul <[e-mail]:

On Jun 19, 2:32 am, Santhosh <[e-mail]:

Hi to all,
How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?

I do not think it is possible using only bitwise operators because
they work on a base-2 numbering system whereas you want to know the
_decimal_ digits.

[Richard Heathfield]

den2k said:

On 19 Giu, 08:35, rahul <[e-mail]:

>On Jun 19, 2:32 am, Santhosh <[e-mail]:

Hi to all,
How the individual digits of a number can be obtained using the
bitwise operators alone.Is it possible to do it ?

I do not think it is possible using only bitwise operators because
they work on a base-2 numbering system whereas you want to know the
_decimal_ digits.

We have already discussed the fact that addition can be done using the ^,
&, and << operators (XOR for add-without-carry, AND and LSH for obtaining
and moving the carry, repeat until no carry). Given addition, subtraction
is easy - simply take two's complement and add.

Given subtraction, division becomes not only possible but even easy.
Consider 34 / 10 (which we need to do if we're going to get the result 3
and remainder 4). 34 is 100010 in binary, and ten is 1010. Observe long
division in binary, noting that subtraction is done with ^ & << and the
two's complement, comparison can be done by subtraction, isolating the
bits necessary for the trial divisions can be done using shift and AND,
and "bringing down a bit" can be done with shift and OR:

1010)100010
1010 <---- Subtrahend <= minuend? No.

_0000
1010)100010
1010 <---- Subtrahend <= minuend? Yes. Subtract.

_00001
1010)100010
1010
---
111 <----- bring down a bit

_00001
1010)100010
1010
---
1110
1010 <---- Subtrahend <= minuend? Yes. Subtract.

_000011 <---- Result: 3
1010)100010
1010
---
1110
1010
---
100 <---- Remainder: 4

Yes, Virginia, you *can* divide by ten, even if you're thinking in binary.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999