The Joel on Software Discussion Group (CLOSED)

A place to discuss Joel on Software. Now closed.

This community works best when people use their real names. Please register for a free account.

Other Groups:
Joel on Software
Business of Software
Design of Software (CLOSED)
.NET Questions (CLOSED)
TechInterview.org
CityDesk
FogBugz
Fog Creek Copilot


The Old Forum


Your hosts:
Albert D. Kallal
Li-Fan Chen
Stephen Jones

Bitwise Operations!

Hi all,

I am using bitwise operators to use addition which I got from somebody's post. I have caught up with AND, OR, XOR operators on bit level.

Okay, there's one thing to know what each of these operators give you when you compare two binary values for integers. My question is, how would you determine which operators to use in a method to get subtraction, addition and so forth. For example, if I had never found a method for addtion online, how would I go about doing on my own. That is my question.

Any help or direction would help. Thanks.
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
Addition *is* a bitwise operator.
http://en.wikipedia.org/wiki/Adder_(electronics)

Tuesday, June 10, 2008
 
 
For addition, use adders:  http://en.wikipedia.org/wiki/Adder_(electronics)

In the above wiki entry, look at the bottom in the "See also" section for links to subractor and multiplier.
bpd
Tuesday, June 10, 2008
 
 
Hmmm...  Saying "If I didn't know it, how would I find it out" is a rather interesting question.  Perhaps you would just take two integers, convert them to binary, perform some arbitrary bitwise operation on them, and then convert them back again.  Then you might say "Wow - that looks like addition".  Over time you'd need to cope with overflow, signed numbers etc etc.

That's a different thing to saying "How would I make a formal proof".
Mr. Jones
Tuesday, June 10, 2008
 
 
"how would you determine which operators to use in a method to get subtraction, addition and so forth"

I probably would draw out a truth table with the binary values and try applying different operations/gates.

I believe addition is achieved by ANDing then XORing.
Josh in Jersey Send private email
Tuesday, June 10, 2008
 
 
I might not have been clear in my post. Example:

public static int sum (int a, int b) {// Adding two numbers without "+" operator
        int x = 0;
        x = a^b;

        while((a&b)!=0) {
            b=(a&b)<<1;
            a=x;
            x=a^b;
        }
        return x;
    }

Now you see the above method, I understand the bitwise operators in it, but you have to know which one to use to produce the end result.

I am trying to learn how to determine the steps. Is there a clear cut formula/definition, if you use & ^ I on binary values of two variable, it will yeild. Like using 2<<3 (multiplication), will give you 8, it's a power of two. Or using 5>>2(division) will give you 1. Thanks!
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
Hi Josh, I think your sounded more like what I was wanting to know. Is there a particular one can read to understand how to plan on understand the truth tables and getting a plan for doing this kind of manipulation. Thanks again.
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
Sorry for the typos. I meant to say "books one can read".
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
Use XOR and AND:

Output bit = a XOR b XOR c
Carry bit for next stage = a AND b

Where 'a' and 'b' are input bits from the two numbers you're adding and 'c' is carry bit from previous stage.
Jimmy Jones
Tuesday, June 10, 2008
 
 
Find an undergraduate EE textbook on basic Digital Logic
farmboy Send private email
Tuesday, June 10, 2008
 
 
Thanks again. I found this link that explains the bitwise like I was looking for but not enough though. I want to understand the concept and how they work.

http://www.lib.tsinghua.edu.cn/chinese/INTERNET/Java/jv08.htm
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
Mr. Smith,

if I understand you right, your question is "How can I develop an algorithm for add/sub using only boolean logic"?

Note that "develop an algorithm" and "boolean logic" are two complete cans of worms in one single question. There is no easy answer, though for your examples:

- Consider the input in binary form.
- Make a manual binary addition (same as in decimal) and observe the flow of information (carry).
- Identify the similarities in each single step.
- Make a list of possible inputs and required outputs for the single steps you identified in the previous point, ie. the truth table.
- Try to come up with a representation for the truth table in binary logic.
- Connect the representations of the single steps to get the full result.

You can represent the complete truth table in one single equation and then try to reduce it as far as possible, eg.

A B Out
0 0 1
0 1 0
1 0 1
1 1 0

Out = (!A & !B) | (A & !B)
<=> Out = (!A | A) & !B
<=> Out = !B

As for truth tables, have a look here:
http://en.wikipedia.org/wiki/Truth_table
Secure
Tuesday, June 10, 2008
 
 
Why would you want to implement your own adder when intel/amd do it for you?

For more complex stuff, get a book on logic system design :) ( a 1st year EE course, you will learn a lot about logic, bits, and low-level stuff)

http://en.wikipedia.org/wiki/Demorgan
http://en.wikipedia.org/wiki/Karnaugh_map

and a lot more .....
Totally Agreeing
Tuesday, June 10, 2008
 
 
I am not trying to implement my own logic nor am I trying to invent the wheel. For example, if someone asks me a question in an interview as to how to add or subtract using bitwise operators. I at least need to take them through the thought process or either just remember the logic by rote and pretend I know.

However, for my own satisfaction and learning, I need to understand how would others do. Like Secure is able to tell me or like others here. I need to know what basic concepts I need to build in order to be able understand the flow. Is that fair enough? :) 

How else will you able differentiate yourself in knowledge and skills if keep coding in Java and not know anything else? It's not just about making money for me but learn something different, that might help me become a better problem solver.
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
Mr. Smith,

The little knowledge I exhibited in my post came from a mix of 9th grade math and playing around with "Bread Boards" in college.

If I understand you correctly you want to know how to determine what bit operations give you the correct result without using trial and error.

I don't know if there is purely mathematical method that would apply in this situation.  To me it makes the most sense to just try different combination of bit operations..there are few enough to make this feasible.

If you wanted to program this behavior I would just go thru all of the bit ops and compare them to know values.
Josh in Jersey Send private email
Tuesday, June 10, 2008
 
 
I find this an interesting post.....before a solution can be appropriately provided for you regarding this issue, it is important to know exactly what it is you are trying to do?

Perhaps there is a different approach to achieving a solution that has nothing to do with bitwise operators.

Under what situation do you need to know whether a variable or constant is a 1 or 0?????

Not sure I understand what it is you are trying to achieve. If you are trying to determine if one string equals another, there are many other ways of successfully approaching this without using bitwise operators....
Brice Richard Send private email
Tuesday, June 10, 2008
 
 
You're essentially asking how someone would learn to build an Arithmatic Logic Unit (ALU).  The best way to learn is to do it.  The next best is to read a book about it.

It gets really fun when you want to learn how to implement floating-point operations.

The problem I think we're having with your question is it's kind of like asking "how do I learn how to explain the steps you take in doing long-hand division, without understanding addition, subtraction, multiplication and remainders?"  Well, you can't.  To really understand how long-hand division works, you need to understand all of those concepts.

To really understand how that code to do addition WORKS, you need to understand the binary representation of integers and the logical operations you can do on binary representations, and how they're related.  Really, for your specific question, it comes down to understanding BASE-2 arithmatic, and understanding carrying bits.

If you add 1 and 1, you get zero (and you have to carry one.)  If you add 1 and 0, you get 1 (and you have nothing to carry.)  If you add 0 and 0, you get 0 (and you have nothing to carry.)

If you understand that ^ means XOR, and that says "one of these OR the other, but not both", you can figure out that that step of your program is trying to add all of the bits to eachother, but ignoring the carry part.

If you understand that ^ means AND, and that says, "both of these", you can figure out that that step of your program is trying to add all of the bits to eachother, and figuring out when it has to carry.

If you understand that << 1 means shift left one, then you can see that it's taking the AND part, and CARRYING it.

Try writing out a couple examples, and following the binary operations one step at a time.  Add 2 and 8.  Add 3 and 2.  Add 7 and 1.  See how it flows, and UNDERSTAND each step...

That's about as close as I can get you.  Best of luck!
Matt Cruikshank Send private email
Tuesday, June 10, 2008
 
 
I think I deduce that I should get a digital logic book and that might be the answer I was looking for. Thanks everyone for their help.
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
If you are trying to create any kind of algorithm that is associated to encryption protocols, your best bet would be to use functions that ALREADY exist for this purpose so that you don't go re-inventing the wheel.

The .Net framework has some really nice methods and function calls to achieve this objective.

I can't fathom a reason outside the scope of some sort of security or encryption effort in which determining what binary bit a character has would be of any significance in an application.
Brice Richard Send private email
Tuesday, June 10, 2008
 
 
Encrypt data that is sensitive to your application by putting it on the clipboard. They will never find it! If it is a file, they could just find the directory. I have proposed a much better solution. Thinking about bitwise operators is completely the wrong way.

Tuesday, June 10, 2008
 
 
" think I deduce that I should get a digital logic book and that might be the answer I was looking for. Thanks everyone for their help."

You might try Charles Petzold's book "Code: The Hidden Language of Computer Software and Hardware". Much of the book is devoted to exactly what you seem to be looking for: how arithmetic operations are built from Boolean operations. It is written for a non-technical audience and I think you'll find it very clear.

http://www.charlespetzold.com/code/
Charles E. Grant Send private email
Tuesday, June 10, 2008
 
 
"do you need to know whether a variable or constant is a 1 or 0.... if you are trying to determine if one string equals another.... If you are trying to create any kind of algorithm that is associated to encryption protocols...."

Brice, smoking the hole package of dope at once, alone, without sharing it with your friends, AGAIN????

You really shouldn't do that, it's no good for you.
...
Tuesday, June 10, 2008
 
 
First, don't listen to people who tell you not to reinvent the wheel.  If you're curious and want to learn, wheel reinventing is actually good.
Start by writing down the algorithm for longhand addition in decimal notation.  Then think what's going to change if you do the same in binary rather than decimal notation.  It isn't that different.  Finally, compare your algorithm to one from any book on digital circuit design.  Extra credit if you reinvent two's complement for negative numbers.
Jeff Zanooda Send private email
Tuesday, June 10, 2008
 
 
Mr. Smith, by all means pursue your intellectual curiosity wherever it leads you. Do not listen to the naysayers and "pragmatists."

Your question is covered in the introductory Digital Logic course for EE sophomores. Back in the day, all EECS students learned this. I guess CS courses may not include this, bit I think it is a shame. I do not have a handy reference to recommend, because my coursework was a looong time ago and the texts would be out of print. If you visit your nearest university bookstore you can find a Digital Logic text for EE undergraduates that will broaden your horizons, and likely make you a better programmer. (Look for "ripple counter" and "shift adder" in the index.)
Mikkin
Tuesday, June 10, 2008
 
 
Guys :)

I am not looking for encrytion protocols or nothing such that. I was simple looking for some help for directions for my curiosities and to learn something under the hood to open up my brain with fresh ideas.

I will look into the book suggested and thanks to last two posters. End of this thread.
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
I found these books on amazon with very good review. I think these books will hopefully give me what I need, and I will go from there.

Books:
Code: The Hidden Language of Computer Software and Hardware by Charles Petzold

Fundamentals of Digital Logic and Microcomputer Design, 5th Edition (Hardcover)

Thanks for everyone, who suggested from smoking weed to encryption protocols algorithm.
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
I suggest before buying any books find tutorials from the net, or online class notes from universities.
Rick Tang
Tuesday, June 10, 2008
 
 
A source of inspiration with bit twiddling hacks: http://graphics.stanford.edu/~seander/bithacks.html
Karel Thönissen Send private email
Tuesday, June 10, 2008
 
 
Thanks for the suggestion and the link. I am just looking for a book that will take me step by step process of teaching with examples.

After the advent of Java and more object-oriented languages, even though I am a Java programmer, it's hard to find books on these topics. Mostly just touch this area and that's it.
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
Matt Cruikshank!

You have summed it up for me, that's exactly I want to learn. I missed your post earlier but I just noticed. I need to understand the arithmatic concepts for binary and the understand how using AND, OR, XOR uses them so that I can do the addition, subtraction, or mulitplication with integers using bitwise operators in Java.
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
That's no fun.

Either use C, or Java bytecodes :)
Rick Tang
Tuesday, June 10, 2008
 
 
I actually I do want to learn C and have fascination with it. I am just surprised that colleges don't teach C anymore for CIS majors. Instead, we had to sit through those VB classes, and were told it was object-oriented. :)
Mr. Smith Send private email
Tuesday, June 10, 2008
 
 
Others have recommended reading a book on digital logic (a.k.a. discrete mathematics), which is certainly one valid approach.  But it seems to me that your interests go a little deeper than that since you expressed an interest in the underlying theory that would allow one to devise such an algorithm (and verify that it is a correct one).  A more general approach to these kinds of problems would fall under the branch of mathematics known as Number Theory.  So, you may be interested in checking out an introductory text on that subject as well.
Matt
Wednesday, June 11, 2008
 
 
Have a look at this site: http://woodgears.ca/marbleadd/. This guy has built a "Binary Marble Adding Machine". This provides an excellent way to see how addition in binary works.
Roy
Wednesday, June 11, 2008
 
 
So many posts, and nobody mentions http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654/
 ? I am shocked!
ping?
Wednesday, June 11, 2008
 
 
I was looking for that book but couldn't remember the title. It was driving me mad yesterday.
Bart Park
Wednesday, June 11, 2008
 
 
Mikkin
Wednesday, June 11, 2008
 
 
Dude,

How do you perform addition on paper, in base 10? Think about the algorithm you were taught in school.

Now, think about how to adapt that algorithm for base 2. Think about how to do it one Bit at a time.

Now, think about how to implement that algorithm using bitwise operators. To get and set one bit at a time, you'll need to use masks and shifting in combination with C's bitwise operators.

Once you've got that down, then you could start thinking about shortcuts.

But, you'll find there's no easy shortcut that lets you perform the whole addition on all bits at once using bitwise and, or and negation. Because the result bit can depend on all the lower bits in the addends, not just on the corresponding bits.
Matt
Wednesday, June 11, 2008
 
 
Thanks for your responses and very useful links for the books. By the way, I have already learned the arithmetic in binary and understand the bitwise operators. I am reading more and will get there.

In the meanwhile, I am also learning C and want to do all this in C language. I am always handling many things at one time hoping on different things :).

I want to ask you, is there any software that will allow me to compile C code in XP? Any freeware out there? Thanks again for all the helpful replies.
Mr. Smith Send private email
Wednesday, June 11, 2008
 
 
Rick Tang
Wednesday, June 11, 2008
 
 
Thanks for the link. I tried digital mars but it prints funyy for hello world. See below:

C:\ccode>\dm\bin\dmc hello
link hello,,,user32+kernel32/noi;

I was hoping someone woould tell me if they have used a freeware one that works good.
Mr. Smith Send private email
Wednesday, June 11, 2008
 
 
That doesn't work???

It compiles to create a binary exe. You run the resulted exe.
Rick Tang
Wednesday, June 11, 2008
 
 
Worst case is you can get the visual studio c++ express edition and use that if the other compilers are giving you fits. From 2005 on they are reasonably standards compliant.
Bart Park
Wednesday, June 11, 2008
 
 
Oh! I got it! duhhh! It works. Thanks.
Mr. Smith Send private email
Wednesday, June 11, 2008
 
 
Guys,

I am using CDT and MinGW, installed it with Eclipse.

Verified the MinGW is setup right, using gcc -v command.
Created a standard C project with a hello.c source file.

How do I create the exe file and want to run.
It does show me this messaged in Problem console.

Error launching 'cygpath' command.

Any help or suggestions would be great. Thanks.
Mr. Smith Send private email
Thursday, June 12, 2008
 
 
Mr. Smith Send private email
Thursday, June 12, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz