hi,

I need to write a function that will check whether x is nonzero. Return 0
if x is = to 0 and 1 otherwise. The open operators I can use are ~ & ^ | +
<< >> and I am not allowed to use an loops.

My program so far looks like:

int isNonZero(int x) {


x = (1 << x) & x;
x = ~x;
x = x & 1;
return x;


}

All cases work except for the below.


Test isNonZero(-2147483648[0x80000000]) failed.
Gives 0[0x0]. Should be 1[0x1]

If tried everything I could think of and I am all out of ideas. Any one
have any idea how I could fix my code to deal with this negative number?


I also need to write one that will check whether x is nonzero using only ~
& ^ | + << >> 

My code so far is:
int isLess(int x, int y) {

int a =0;

a = x ^ y;
a = y >> a;
a = a + 1;
a  = !a;
  return !a;
}

Which only works for about half the cases (on small non-negative numbers)


Any input would be appreciated.
Thanks,

77scrapper77 wrote:
> 
> I need to write a function that will check whether x is nonzero. Return 0
> if x is = to 0 and 1 otherwise. The open operators I can use are ~ & ^ | +
> << >> and I am not allowed to use an loops.
> 
> My program so far looks like:
> 
> int isNonZero(int x) {
> 
> x = (1 << x) & x;

Undefined behaviour for most values of x. The Standard has this to
say about bit-shifting:

"If the value of the right operand is negative or is greater than
or equal to the width in bits of the promoted left operand, the
behavior is undefined."

Also, = is an operator, and it's not in your list of allowed operators.

Personally, I don't think it's possible in correct C with just the
operators that you are allowed to use (although I am ready to be
proved wrong).

77scrapper77 wrote:
> hi,
> 
> I need to write a function that will check whether x is nonzero. Return 0
> if x is = to 0 and 1 otherwise. The open operators I can use are ~ & ^ | +
> << >> and I am not allowed to use an loops.
> 
> My program so far looks like:
> 
> int isNonZero(int x) {
This function name invades the implementation's namespace
as it starts with "is". Make that IsNonZero().
> 
> 
> x = (1 << x) & x;

Undefined behaviour, see infobahn's message.

> x = ~x;
> x = x & 1;
> return x;
> 
> 
> }
> 
> All cases work except for the below.

Nope: x=0 ... (~((1<<0) & 0)) & 1 == 1.
So your most important case does not work.

I do not see at all how you can do anything sensible for signed
integers as they could have negative zeros for 1s complement and
sign-magnitude representations. Seems to be a completely hopeless
task. Even for 2s complement only, I do not have the least clue
how to do it.

> Test isNonZero(-2147483648[0x80000000]) failed.
> Gives 0[0x0]. Should be 1[0x1]
> 
> If tried everything I could think of and I am all out of ideas. Any one
> have any idea how I could fix my code to deal with this negative number?

No. Not at all.


> I also need to write one that will check whether x is nonzero using only ~

ITYM whether x<y

> & ^ | + << >> 
> 
> My code so far is:
> int isLess(int x, int y) {

Again: The function name.

> int a =0;
> 
> a = x ^ y;
> a = y >> a;

You seem to be completely clueless what the shift operators are doing.

> a = a + 1;
> a  = !a;
>   return !a;

! is an operator, too, and not on your list.
If it was not, your IsNonZero() function's body would consist of
{return !!x;}

> }
> 
> Which only works for about half the cases (on small non-negative numbers)
> 
> Any input would be appreciated.

Are you allowed to use if, else, ...?
Either you are not telling us the whole truth or you should look
for someone different to give you C problems.


Cheers
  Michael
-- 
E-Mail: Mine is an   /at/ gmx /dot/ de   address.

"77scrapper77" <gregarious_girl77@nospam.hotmail.com> writes:

> I need to write a function that will check whether x is nonzero. Return 0
> if x is = to 0 and 1 otherwise. The open operators I can use are ~ & ^ | +
> << >> and I am not allowed to use an loops.

int is_nonzero (int x)
{
    switch (x) {
    case 0:
       return 0;
    default:
       return 1;
    }
}
-- 
"Some programming practices beg for errors;
 this one is like calling an 800 number
 and having errors delivered to your door."
--Steve McConnell

77scrapper77 wrote:
> hi,
>
> I need to write a function that will check whether x is nonzero.
Return 0
> if x is = to 0 and 1 otherwise. The open operators I can use are ~ &
^ | +
> << >> and I am not allowed to use an loops.
> 

int isNonZero(int x)
{
  if (x)
    return 1;
  return 0;
}

I can't use any loops or if statements. I can use = though. 

int isNonZero(int x) {
    return(x || 0);
} 

On Sun, 20 Feb 2005 19:55:08 +0100, Michael Mair 
   <Michael.Mair@invalid.invalid> wrote:

> 77scrapper77 wrote:
>> hi,
>> 
>> I need to write a function that will check whether x is nonzero. Return 0
>> if x is = to 0 and 1 otherwise. The open operators I can use are ~ & ^ | +
>> << >> and I am not allowed to use an loops.
>> 
>> My program so far looks like:
>> 
>> int isNonZero(int x) {
> This function name invades the implementation's namespace
> as it starts with "is". Make that IsNonZero().

Not true.  From section 7.26 "Future Library Directions":

  7.26.2 Character handling <ctype.h>
  
  1 Function names that begin with either is or to, and a lowercase
    letter may be added to the declarations in the <ctype.h> header.

It is allowed to start an identifier with is and an uppercase letter,
which is what he did.  The same is true as far as I can see with most of
the other namespace restrictions (function names starting with str, mem
or wcs ans a lowercase letter are banned, ones with an uppercase letter
are permitted).

> Are you allowed to use if, else, ...?
> Either you are not telling us the whole truth or you should look
> for someone different to give you C problems.

It looks like homework to me...

Chris C

I can't use || either, just |.

Chris Croughton <chris@keristor.net> writes:

> <Michael.Mair@invalid.invalid> wrote:
>> 77scrapper77 wrote:
>>> int isNonZero(int x) {
>> This function name invades the implementation's namespace
>> as it starts with "is". Make that IsNonZero().
>
> Not true.  From section 7.26 "Future Library Directions":
>
>   7.26.2 Character handling <ctype.h>
>   
>   1 Function names that begin with either is or to, and a lowercase
>     letter may be added to the declarations in the <ctype.h> header.

However, C89 implementations are allowed to have a
case-insensitive linker.
-- 
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
 \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

On 2005-02-20 12:45:49 -0500, "77scrapper77" 
<gregarious_girl77@nospam.hotmail.com> said:

> hi,
> 
> I need to write a function that will check whether x is nonzero. Return 0
> if x is = to 0 and 1 otherwise. The open operators I can use are ~ & ^ | +
> << >> and I am not allowed to use an loops.

In C99:

int isNonZero(int x)
{
  _Bool b = x;
  return b;
}

-- 
Clark S. Cox, III
clarkcox3@gmail.com

Michael Mair wrote:
> ! is an operator, too, and not on your list.
> If it was not, your IsNonZero() function's body would consist of
> {return !!x;}
> 
>> }

This has it. That's the first thing I thought of. Any excuse to stack up 
operators.

If you don't like that then, try return !!!!x; instead


It's best not to use tricks though, readability is paramount.

also, this will suffice, return x ? 1 : 0 ;

I can't use the ! operator.

"77scrapper77" <gregarious_girl77@nospam.hotmail.com> writes:
> I can't use any loops or if statements. I can use = though. 

Then you should have said so in the first place.  Old Wolf's solution
satisfied the constraints you originally posted.  You can't expect
much help if you change the problem statement.

The problem statement doesn't look like anything even vaguely useful.
Is it a homework assignment?

-- 
Keith Thompson (The_Other_Keith) kst-u@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.

77scrapper77 wrote:
> I need to write a function that will check whether x is nonzero.
Return 0
> if x is = to 0 and 1 otherwise. The open operators I can use are ~ &
^ | +
> << >> and I am not allowed to use an loops.

Well, hopefully this hint will not be enough that you don't still have
to do some thinking:

0x0 + 0x3 = 0x3 (011b)
0x1 + 0x3 = 0x3 (100b)
0x2 + 0x3 = 0x3 (101b)
0x3 + 0x3 = 0x3 (110b)

-Chris

Chris Williams wrote:
> 
> 77scrapper77 wrote:
> > I need to write a function that will check whether x is nonzero.
> Return 0
> > if x is = to 0 and 1 otherwise. The open operators I can use are ~ &
> ^ | +
> > << >> and I am not allowed to use an loops.
> 
> Well, hopefully this hint will not be enough that you don't still have
> to do some thinking:
> 
> 0x0 + 0x3 = 0x3 (011b)
> 0x1 + 0x3 = 0x3 (100b)
> 0x2 + 0x3 = 0x3 (101b)
> 0x3 + 0x3 = 0x3 (110b)

But it has to work for /any/ int. Consider the case where x is
equal to INT_MAX. Adding any non-negative value to x would then
result in undefined behaviour (integer overflow).

> Chris Williams wrote:
> > Well, hopefully this hint will not be enough that you don't still
have
> > to do some thinking:
> >
> > 0x0 + 0x3 = 0x3 (011b)
> > 0x1 + 0x3 = 0x4 (100b)
> > 0x2 + 0x3 = 0x5 (101b)
> > 0x3 + 0x3 = 0x6 (110b)

[corrected above table]

infobahn wrote:
> But it has to work for /any/ int. Consider the case where x is
> equal to INT_MAX. Adding any non-negative value to x would then
> result in undefined behaviour (integer overflow).

True, I was assuming a machine where INT_MAX + 1 == INT_MIN, which is
unsafe given a wide enough a range of platforms. Although you can get
around this by only testing up to INT_MAX >> 1 and then using secret,
magic bit twiddling for everything else.
However, spending a few minutes trying to solve this with completely
portable code (e.g. CHAR_BIT could equal 7) but without * / or -, I can
say that undefined behavior is the least of ones worries. I think I can
determine how many bits are in an int, but if I then want to do a right
shift by one less than the total bit count, I am at a loss how to do it
without minus.

int uintBits =  /*I would have to assume there is a better way, but for
the moment brute force it is */
   /* One byte's worth of bits */
   CHAR_BIT +

   /* C will treat CHAR_BIT as an integer, so by shifting left a bytes
worth and back we will either get CHAR_BIT or 0 dependent on whether
the platform supoorts two byte ints */
   ((CHAR_BIT << CHAR_BIT) >> CHAR_BIT) +

   /* If we can move over two then we can add on two more byte's worth
since an int will be either two or four bytes not three (so far as I am
aware) */
   (((CHAR_BIT << (CHAR_BIT << 1)) >> (CHAR_BIT << 1)) << 1)
;
int highBit = value >> (uintBits - 1);  //but no minus allowed!!

-Chris

infobahn <infobahn@btinternet.com> spoke thus:

> Personally, I don't think it's possible in correct C with just the
> operators that you are allowed to use (although I am ready to be
> proved wrong).

I'm sure there's something wrong with

(x<<1)==(x>>1);

but I'm not exactly sure what.

-- 
Christopher Benson-Manica  | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org    | don't, I need to know.  Flames welcome.

Christopher Benson-Manica wrote:
> 
> infobahn <infobahn@btinternet.com> spoke thus:
> 
> > Personally, I don't think it's possible in correct C with just the
> > operators that you are allowed to use (although I am ready to be
> > proved wrong).
> 
> I'm sure there's something wrong with
> 
> (x<<1)==(x>>1);
> 
> but I'm not exactly sure what.

The == is wrong, because it's not in the list of allowed operators.

Nice try, though.

Chris Williams wrote:
> 
> > Chris Williams wrote:
> > > Well, hopefully this hint will not be enough that you don't still
> have
> > > to do some thinking:
> > >
> > > 0x0 + 0x3 = 0x3 (011b)
> > > 0x1 + 0x3 = 0x4 (100b)
> > > 0x2 + 0x3 = 0x5 (101b)
> > > 0x3 + 0x3 = 0x6 (110b)
> 
> [corrected above table]
> 
> infobahn wrote:
> > But it has to work for /any/ int. Consider the case where x is
> > equal to INT_MAX. Adding any non-negative value to x would then
> > result in undefined behaviour (integer overflow).

s/non-negative/positive/   (oops)

<snip>
> 
>    /* If we can move over two then we can add on two more byte's worth
> since an int will be either two or four bytes not three (so far as I am
> aware) */

It must have a sign bit and at least 15 value bits, but it can be
one byte, or two, or three, or four, or five, or eight, or even
thirty-seven. I have worked on systems with 1-, 2-, and 4-byte
ints, and I know of at least one system with 8-bit bytes.

77scrapper77 wrote:
> hi,
> 
> I need to write a function that will check whether x is nonzero. Return 0
> if x is = to 0 and 1 otherwise. The open operators I can use are ~ & ^ | +
> << >> and I am not allowed to use an loops.
> 
> My program so far looks like:
> 
> int isNonZero(int x) {
> 
> 
> x = (1 << x) & x;
> x = ~x;
> x = x & 1;
> return x;
> 
> 
> }

I am not sure if standard defines the case when you are shifting left by 
more than the bit size of integer.

But how about:

   N-1
   ---
[ \   (x >> i) ] & 1
   /
   ---
   i=0

where N is the bit size of word, so for 4 bit machine the expression is:

( x + (x>>1) + (x>>2) + (x>>4) ) & 1

>   N-1
>   ---
> [ \   (x >> i) ] & 1
>   /
>   ---
>   i=0
> 
> where N is the bit size of word, so for 4 bit machine the expression is:
> 
> ( x + (x>>1) + (x>>2) + (x>>4) ) & 1

correction:

( x + (x>>1) + (x>>2) + (x>>3) ) & 1

infobahn wrote:
> Chris Williams wrote:
> >    /* If we can move over two then we can add on two more byte's
worth
> > since an int will be either two or four bytes not three (so far as
I am
> > aware) */
>
> It must have a sign bit and at least 15 value bits, but it can be
> one byte, or two, or three, or four, or five, or eight, or even
> thirty-seven. I have worked on systems with 1-, 2-, and 4-byte
> ints,

How does one get "a sign bit and at least 15 value bits" with 1-byte
ints? Or is this a platform with 16-bit bytes?

> and I know of at least one system with 8-bit bytes.

8-bit bytes? x86?

But back to the drawing board I guess for my bit-count determiner =)

-Chris

roman ziak wrote:
>>   N-1
>>   ---
>> [ \   (x >> i) ] & 1
>>   /
>>   ---
>>   i=0
>>
>> where N is the bit size of word, so for 4 bit machine the expression is:
>>
>> ( x + (x>>1) + (x>>2) + (x>>4) ) & 1
> 
> 
> correction:
> 
> ( x + (x>>1) + (x>>2) + (x>>3) ) & 1

sorry, one more correction:

( x | (x>>1) | (x>>2) | (x>>3) ) & 1

this should be the last :)

Chris Williams wrote:
> 
> infobahn wrote:
> >
> > It must have a sign bit and at least 15 value bits, but it can be
> > one byte, or two, or three, or four, or five, or eight, or even
> > thirty-seven. I have worked on systems with 1-, 2-, and 4-byte
> > ints,
> 
> How does one get "a sign bit and at least 15 value bits" with 1-byte
> ints? Or is this a platform with 16-bit bytes?

32, in my case.

> 
> > and I know of at least one system with 8-bit bytes.
> 
> 8-bit bytes? x86?

Bigtime typo. I meant 8-byte ints.

In article <42191fc9@x-privat.org>, spacenjasset@yahoo.co.uk says...
> Michael Mair wrote:
> > ! is an operator, too, and not on your list.
> > If it was not, your IsNonZero() function's body would consist of
> > {return !!x;}
> > 
> >> }
> 
> This has it. That's the first thing I thought of. Any excuse to stack up 
> operators.
> 
> If you don't like that then, try return !!!!x; instead
> 
> 
> It's best not to use tricks though, readability is paramount.
> 
> also, this will suffice, return x ? 1 : 0 ;


Why are doing obvious homework assignments, no matter how trivial?
 

-- 
Randy Howard (2reply remove FOOBAR)
"Making it hard to do stupid things often makes it hard
 to do smart ones too." -- Andrew Koenig

Randy Howard wrote:
> 
> Why are doing obvious homework assignments, no matter how trivial?

I don't think we did, unless you count "this homework assignment
is impossible" as "doing" the assignment.

77scrapper77 wrote:
> hi,
>
> I need to write a function that will check whether x is nonzero.
Return 0
> if x is = to 0 and 1 otherwise. The open operators I can use are ~ &
^ | +
> << >> and I am not allowed to use an loops.
>

<snip>


#include <stdio.h>
#include <stdint.h>

int func(uint32_t x)
{
	return ~((x - 1) & ~x & 0x80000000u) >> 31;
}


I think this should work.  Needs C99 for the exact width unsigned
integer type.


Mark F. Haigh
mfhaigh@sbcglobal.net

"Mark F. Haigh" wrote:
> 
> 77scrapper77 wrote:
> > hi,
> >
> > I need to write a function that will check whether x is nonzero.
> Return 0
> > if x is = to 0 and 1 otherwise. The open operators I can use are ~ &
> ^ | +
> > << >> and I am not allowed to use an loops.
> >
> 
> <snip>
> 
> #include <stdio.h>
> #include <stdint.h>
> 
> int func(uint32_t x)
> {
>         return ~((x - 1) & ~x & 0x80000000u) >> 31;
> }
> 
> I think this should work.  Needs C99 for the exact width unsigned
> integer type.

Even if we take C99 for granted (and that's a big if), what if
UINT_MAX < 0x80000000u ?

infobahn wrote:
> "Mark F. Haigh" wrote:
> 
>>77scrapper77 wrote:
>>
>>>hi,
>>>
>>>I need to write a function that will check whether x is nonzero.
>>
>>Return 0
>>
>>>if x is = to 0 and 1 otherwise. The open operators I can use are ~ &
>>
>>^ | +
>>
>>><< >> and I am not allowed to use an loops.
>>>
>>
>><snip>
>>
>>#include <stdio.h>
>>#include <stdint.h>
>>
>>int func(uint32_t x)
>>{
>>        return ~((x - 1) & ~x & 0x80000000u) >> 31;
>>}
>>
>>I think this should work.  Needs C99 for the exact width unsigned
>>integer type.

C99 does not guarantee the exact width integer types.

> Even if we take C99 for granted (and that's a big if), what if
> UINT_MAX < 0x80000000u ?

You know it, I know it, so let's just sing it together:
  0x80000000ul


Cheers
  Michael
-- 
E-Mail: Mine is an   /at/ gmx /dot/ de   address.

infobahn wrote:
> "Mark F. Haigh" wrote:
> >
> > 77scrapper77 wrote:
> > > hi,
> > >
> > > I need to write a function that will check whether x is nonzero.
> > Return 0
> > > if x is = to 0 and 1 otherwise. The open operators I can use are
~ &
> > ^ | +
> > > << >> and I am not allowed to use an loops.
> > >
> >
> > <snip>
> >
> > #include <stdio.h>
> > #include <stdint.h>
> >
> > int func(uint32_t x)
> > {
> >         return ~((x - 1) & ~x & 0x80000000u) >> 31;
> > }
> >
> > I think this should work.  Needs C99 for the exact width unsigned
> > integer type.
>
> Even if we take C99 for granted (and that's a big if), what if
> UINT_MAX < 0x80000000u ?

Huh?  With C99, if 0x80000000u is not representable as an unsigned int,
it becomes a unsigned long.

But it's not really production code we're talking about here, is it?


Mark F. Haigh
mfhaigh@sbcglobal.net

Michael Mair wrote:
> 
> infobahn wrote:
> > "Mark F. Haigh" wrote:
> >
> >>int func(uint32_t x)
> >>{
> >>        return ~((x - 1) & ~x & 0x80000000u) >> 31;
> >>}
> >>
> >>I think this should work.  Needs C99 for the exact width unsigned
> >>integer type.
> 
> C99 does not guarantee the exact width integer types.

And in any case, the OP specified int, not uint32_t