Sign in to follow this  

Implementing bitwise not operation with only or and and?

This topic is 1125 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I've come across a homework problem for an assembly language/computer architecture class I'm taking that really has me stumped... There's a question asking how to implement the not operation using only or operations and and operations. There were some similar problems where I had to implement or with only and and not operations, and there was one to implement and with only not and or. What I can't figure out, though is how I'm supposed to implement not with only and and or. Is it even possible to do so? I'm starting to wonder if this is a trick question.

Share this post


Link to post
Share on other sites

This can't be done. If you start with 0, 1 and x and you apply OR in any possible way, you only get 0, 1 and x back, and the same is true with AND. So any tree of OR and AND applied to 0, 1 and x will only give you back 0, 1 or x. In order to get NOT(x) you need more ingredients.

Edited by Álvaro

Share this post


Link to post
Share on other sites

If the only options available to you are & and | and a single variable, you can't do it.

 

But give me some little bit more -- such as a conditional, an xor, even the pair of addition and bit shifting or addition and bit masking -- and it becomes quite feasible.  

 

This is probably the lesson your instructor wanted you to learn with the question.

Share this post


Link to post
Share on other sites

The wording is a bit confusing on conditionals, because if I take the question as literally as I'm inclined to do, then I can't use them because they're a comparison instruction followed by one of the conditional jump instructions, which would be an instruction that isn't and or or. 

"Suppose the instruction set did not include the not instruction. How do you implement it using only and and or instructions" really sounds to me like those are the only instructions I'm allowed to use... It seems like a pretty pointless exercise, so I don't think I'll be missing out on understanding anything if I just answer that it's impossible with only and and or.

 

Although in the interest of trying to get points for it, what if xor was an option? I'm thinking it might be good to just provide an example of what could be done if I used one more instruction. If I copied the initial value to another register with and and or, then wouldn't xor against a mask of all 1s or something along that line produce the result I'm looking for?

Share this post


Link to post
Share on other sites
This is homework. It is to get *YOU* to think, not to get *the community* to think.

There are many different reliable ways to do it. Remember, all you have to do is convert 1 to 0 and convert 0 to 1.

I hinted at five different options that I know would work. Depending on what other operations you have and what assumptions you can make, you might find many more. For example, are you working on a machine that uses 2's compliment numbers (like nearly all integer numbers these days)? What do negative numbers look like, relative to positive ones? Can you use that? There is a sixth potential option.

Share this post


Link to post
Share on other sites

This topic is 1125 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this