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.
Implementing bitwise not operation with only or and and?
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.
Any function you build out of only AND and OR that takes one input will be idempotent. NOT is not idemponent, therefore you cannot construct NOT using only AND and OR.
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.
Author
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?
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.
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.
Author
Okay, thanks. I'll try and see what I can come up with. At least now I have a direction to go with it.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
