LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 06-30-2008, 02:49 AM   #16
ErV
Senior Member
 
Registered: Mar 2007
Location: Russia
Distribution: Slackware 12.2
Posts: 1,202
Blog Entries: 3

Rep: Reputation: 62

Quote:
Originally Posted by graemef View Post
Possibly something that operates at the bit rather than byte level?
So, do you think that addition (and asm's icrement operation) doesn't operate on bit level?

Last edited by ErV; 06-30-2008 at 03:23 AM.
 
Old 06-30-2008, 02:58 AM   #17
jlliagre
Moderator
 
Registered: Feb 2004
Location: Outside Paris
Distribution: Solaris 11.4, Oracle Linux, Mint, Debian/WSL
Posts: 9,789

Rep: Reputation: 492Reputation: 492Reputation: 492Reputation: 492Reputation: 492
Increment alter bits but isn't technically a bit operator.
Bit operators are distinct from arithmetic ones and others.

There are five bitwise operators in C:
& | ^ << and >>.
 
Old 06-30-2008, 03:23 AM   #18
ErV
Senior Member
 
Registered: Mar 2007
Location: Russia
Distribution: Slackware 12.2
Posts: 1,202
Blog Entries: 3

Rep: Reputation: 62
Quote:
Originally Posted by jlliagre View Post
Increment alter bits but isn't technically a bit operator.
Bit operators are distinct from arithmetic ones and others.

There are five bitwise operators in C:
& | ^ << and >>.
You forgot "~" operator.

Ok, here is addition operation using "bitwise-only" operations, test included (example is in C++, but can be easily converted to pure C):
Code:
#include <stdio.h>

unsigned int add(unsigned int arg1, unsigned int arg2){
	unsigned int result = 0;
	for (int i = 0; i < 32; i++){
	    unsigned int andMask = (arg1 & arg2);
	    unsigned int orMask = arg1 | arg2;
	    arg1 = andMask << 1;
	    arg2 = orMask & ~andMask;
	}
	result = arg1|arg2;
	return result;
}

int main(int argc, char** argv){
	//testing add() function
	bool failed = false;
	for (unsigned int i = 0; i < 256; i++)
		for (unsigned int j = 0; j < 256; j++)
			if (add(i, j) != (i + j)){
				printf("failed with %d, %d", i, j);
				failed = true;
			}
	if (!failed)
		printf("algorithm was correct\n");
	return 0; 
}
Feel free to unwrap loop in add() function, so no non-bitwise arithmetics will be involved.

So the end result (calculating negative number using bitwise-only calculations) will be:
Code:
#include <stdio.h>

unsigned int add(unsigned int arg1, unsigned int arg2){
	unsigned int result = 0, andMask, orMask;

#define M andMask = (arg1 & arg2); orMask = arg1 | arg2; arg1 = andMask << 1; arg2 = orMask & ~andMask;
	M M M M M M M M
	M M M M M M M M
	M M M M M M M M
	M M M M M M M M
#undef M
	
	result = arg1|arg2;
	return result;
}

int neg(int x){
	return (int)add(~((unsigned int)x),1);
}

int main(int argc, char** argv){
	//testing add() function
	bool failed = false;
	for (unsigned int i = 0; i < 256; i++)
		for (unsigned int j = 0; j < 256; j++)
			if (add(i, j) != (i + j)){
				printf("add(%d, %d) failed\n", i, j);
				failed = true;
			}
	if (!failed)
		printf("addition algorithm was correct\n");
	//testing neg() funtion
	failed = false;
	for (int i = -256; i < 256; i++)
		if (neg(i) != -i){
			printf("neg(%d) failed\n", i);
			failed = true;
		}


	if (!failed)
		printf("negative algorithm was correct\n");

	//using neg() function
	int x = -2;
	int y = neg(x);
	printf("%d, %d\n", x, y);
	return 0; 
}
Technically, addind 1 to number can be made easier, but that'll require if operator and a loop with arithmetics.

Honestly, it's all pointless. All cpu's support "add" and "neg" operation (I'm not sure if it's called "neg", but it's certainly supported). So there is no sense in using bitwise operations only for negating numbers.

P.S. And I still think OP could guess it himself.

Last edited by ErV; 06-30-2008 at 03:50 AM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 08:09 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration