?
Solved

Implementing Bitwise Operators

Posted on 2003-02-26
21
Medium Priority
?
202 Views
Last Modified: 2010-04-15
Hello -

I am wondering if anyone knows how to implement the logical not (!) operator.  I am developing a program, and it requires me to implement the logical NOT operator using only >> << + | & and ~.  Yes, this is for a class, and I understand if you feel morally obliged to not give me the whole answer, but I have been working on this for quite a while now, and I am completely stumped.  If someone might be able to give me a hint, that would be very much appreciated.

Thanks -

~ace
0
Comment
Question by:Topace
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
  • 3
  • +7
21 Comments
 
LVL 12

Expert Comment

by:rajeev_devin
ID: 8032082
In C use have available the not operator (~), then what is the use of implementing it. Or, are you talking about something else. Comments ???
0
 
LVL 8

Expert Comment

by:akshayxx
ID: 8032164
~ is bitwise  NOT a.. while ! is logical NOT ..
the asker wants to implement logical NOT .. using the mentioned operators
0
 
LVL 12

Expert Comment

by:rajeev_devin
ID: 8032229
you are trying to implement the logical NOT operator using the bitwise operators (<< >> + | & ~). Let me try to solve your problem. You try this simple module

bool NOT(bool x)
{
     x = !x;
     return(x);
}

Let me know if it works.

regards
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 8

Expert Comment

by:ssnkumar
ID: 8032310
Operators are implemented inside a compiler. It's part of the language. I don't think C provides facility to implement your own operators.
The only thing you can do is implement functions which mimics operators.

-Narendra
0
 
LVL 1

Expert Comment

by:cybeonix
ID: 8032655
#define NOT(x) x > 0 ? 1 : 0
0
 
LVL 12

Expert Comment

by:rajeev_devin
ID: 8032679
I totally agree with ssnkumar. Operators cannot be implemented. Thats' why I have provided you a function which mimics the logical NOT operator. Check it out...
0
 
LVL 12

Expert Comment

by:rajeev_devin
ID: 8032827
I totally agree with ssnkumar. Operators cannot be implemented. Thats' why I have provided you a function which mimics the logical NOT operator. Check it out...
0
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 8034163

This is Computer Science 101.


Look in your textbook.


0
 
LVL 1

Author Comment

by:Topace
ID: 8034478
See, the thing is that I am trying to implement a function that will implement the logical NOT operator.  For instance, if I have anything other than zero, it produces zero, while a zero input produces 1.  The deal is that I can only use a certain number of operators, and I am stuck.  

~ace
0
 

Expert Comment

by:pn206
ID: 8034574
Ok, in C a variable is considered true if even one of its bits is 1. It is false if all its bits are 0. So to create a NOT function we need to check every bit in the variable. Return 1 if all the bits are 0 and return 0 if even one bit is 1.

bool NOT(char x)
{
  char r = 0; // will hold the result
  char one = 1;
  int N = 8; // the size of the variable in bits
 
  // loop through every bit in the variable. test each
  // bit and then right shift it out so that the next
  // bit takes its place. OR it with r so that r
  // will equal 1 even if one bit is set to 1
  for(int i=0; i==N; i++) {
    r = r | (x & one);
    x = x>>1;
  }

  // now x is either 1 (if non zero) and 0 (if zero),
  // therefore we need to switch it, the best way to
  // do this is to xor it with 1. then 1^1 = 0 & 0^1 = 0.
  // because we cant use xor we have to make it:
  // A XOR B = (A & (~B)) | (B & (~A))
  r = (r & (~one)) | (one & (~r));

  return r; // this is now either 1 or 0 and will be
            // the same as the logical !
}

Well, I think that should work and I hope it's what you're after.

Prash
0
 

Expert Comment

by:pn206
ID: 8034606
just realised that the function definition is wrong. It should be

char NOT(char x)

Prash
0
 
LVL 8

Expert Comment

by:Exceter
ID: 8034920
>> I totally agree with ssnkumar. Operators cannot be implemented. Thats' why I have provided you a function which mimics the logical NOT operator.

Ditto, this can be done in C++ by overloading an operator but this CANNOT be done in C by a method other than a function.

Exceter
0
 

Expert Comment

by:posternb
ID: 8036007
He isn't trying to overload the operator, just trying to create a function...
How about this:

unsigned char not( unsigned char c ) {
    return (c & 0x01) ^ 0x01;
}

anding c with 1 should result in either 0x00 or 0x01 then if you xor 0x00 with 0x01 you'll get 0x01
conversely if you xor 0x01 with 0x01 you'll get 0x00

I think it should work
0
 

Expert Comment

by:cybervagrant
ID: 8036029
Looks like pn206 is you answer. Could have included a test shell to varify it works :)
0
 
LVL 8

Expert Comment

by:akshayxx
ID: 8038185
>>>>>Ditto, this can be done in C++ by overloading an operator but this CANNOT be done in C by a method other than a function.


macro definitions {group of statements} is for that purpose :)
0
 
LVL 46

Accepted Solution

by:
Kent Olsen earned 400 total points
ID: 8038954

Jumping back into the discussion.....

The problem isn't clearly presented.  The posters here are jumping around trying to offer solutions to different interpretations and have provided several methods that will work.

But this question is right out of beginning Computer Science.  I'm going to offer the correct solution below.  To offer the complete solution would be a violation of the board's policy on homework so I'm going to describe the pieces and let you put them together.

This assignment is trying to teach some of the fundamentals of how computers work.  Mostly for performance, you'll find that many (most) processors use additional inline circuitry rather than looping on repetitive operations.  In fact, even a SHIFT operation is a series of in-line operations.  (That should be a good hint regarding the nature of the solution.)


The problem can be broken down into two major parts.  XORing a bit, and reducing a value down to a single bit.

char NOT (char x)
{
  return ((~x) & 1);
}

will do just fine at toggling the lower bit with the operators available to you.  Pretty basic -- toggle them all and mask the bottom bit.

The XOR than pn206 provided is classic.  But since we only need to change one bit the function can be simpler.


The second half of the problem is a bit trickier.  Reducing a value to a single bit based on whether the original value is non-zero.

But, this is also very straight forward.  The loop in the earlier algorithm violates the terms of the contract by utilizing both comparison and branch.  Here's a reduction of 8 bits to 1 in three steps:

  X |= (X >> 4);
  X |= (X >> 2);
  X |= (X >> 1);

You're welcome to "mask" the result down to the appropriate number of bits but it isn't necessary.


Now put the two pieces together.  Reduce the value to a single bit (in the low-order position) and toggle it.


Good Luck in class.
Kdo

0
 
LVL 8

Expert Comment

by:ssnkumar
ID: 8039239
The negation function is very easy:-)
Just XOR the bit you want to negate with 1.
So, if you want to negate the complete 4 bytes of an integer, then XOR it with 0xffffffff. The result is NOT of that integer (the same you get when you use ~ operator with an integer).
Hope this answers your question.
Since this is very easy, I am not giving the code......I think you can do it very easily....:-)

Feedback is appreciated......

-Narendra
0
 
LVL 8

Expert Comment

by:Exceter
ID: 8044145
>> >>>>>Ditto, this can be done in C++ by overloading an operator but this CANNOT be done in C by a method other than a function.


>> macro definitions {group of statements} is for that purpose :)

Yeah, but a macro isn't an operator. :-)

Exceter
0
 
LVL 1

Author Comment

by:Topace
ID: 8046063
Thanks -

I just needed a hint on how to accomplish it.  Just out of curiosity - how did you know I couldn't use conditionals?  I take it you must have done this assignment.

It is ironic that many of you consider this basic computer science, believe it or not this is a 300 level course.  

Thanks all who helped.


~ace
0
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 8047864

Knowing the answer is a good hint toward knowing the question.

And having an understanding of the hardware goes a long way toward knowing the answer.  ;)


This was part of the first computer design class that I ever took (albeit 28 years ago).  The necessary math was a prereq and the heart of your question goes to the math.  It's kind of scary that this is now a 300 level class.

Kdo

0
 
LVL 1

Author Comment

by:Topace
ID: 8055316
I agree that this is scary that it is a 300 level class - Computer Architecture.  I don't agree with it - I think that basic programming should be taught before high level programming...it would make more logical sense to go in that order.  

It was just a bunch of puzzles...most likely prereqs to information that comes later...but still...

~ace

0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
Suggested Courses
Course of the Month9 days, 13 hours left to enroll

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question