By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,652 Members | 1,337 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,652 IT Pros & Developers. It's quick & easy.

efficient two's complement of a byte array

P: n/a
What would be the most efficient way to calculate the two's complement
of a variable length byte array?
Thanks for your time.

Feb 10 '07 #1
Share this Question
Share on Google+
14 Replies


P: n/a
da*********@gmail.com wrote:
What would be the most efficient way to calculate the two's complement
of a variable length byte array?
I would assume a for loop negating would be good enough
for most purposes.

You could try negating int or long using unsafe code and
a pointer.

Arne
Feb 10 '07 #2

P: n/a
On Feb 10, 12:05 pm, Arne Vajhøj <a...@vajhoej.dkwrote:
darthgha...@gmail.com wrote:
What would be the most efficient way to calculate the two's complement
of a variable length byte array?

I would assume a for loop negating would be good enough
for most purposes.

You could try negating int or long using unsafe code and
a pointer.

Arne
I can't negate int or long because the number could be over 4 billion
digits (in hex). A for loop would do the trick, but I was hoping
someone might know of a different way. Thanks for the thoughts
though.
Chris

Feb 12 '07 #3

P: n/a
On Feb 12, 2:54 pm, darthgha...@gmail.com wrote:
On Feb 10, 12:05 pm, Arne Vajhøj <a...@vajhoej.dkwrote:
darthgha...@gmail.com wrote:
What would be the most efficient way to calculate the two's complement
of a variable length byte array?
I would assume a for loop negating would be good enough
for most purposes.
You could try negating int or long using unsafe code and
a pointer.
Arne

I can't negate int or long because the number could be over 4 billion
digits (in hex). A for loop would do the trick, but I was hoping
someone might know of a different way. Thanks for the thoughts
though.
What Arne was suggesting was an old C trick: looping over the array
one long (64 bits) at a time, negating each long, rather than doing it
a byte at a time. However, as he pointed out, you would have to use
unsafe code to do this.

Feb 13 '07 #4

P: n/a
On Feb 12, 4:56 pm, "Bruce Wood" <brucew...@canada.comwrote:
On Feb 12, 2:54 pm, darthgha...@gmail.com wrote:
On Feb 10, 12:05 pm, Arne Vajhøj <a...@vajhoej.dkwrote:
darthgha...@gmail.com wrote:
What would be the most efficient way to calculate the two's complement
of a variable length byte array?
I would assume a for loop negating would be good enough
for most purposes.
You could try negating int or long using unsafe code and
a pointer.
Arne
I can't negate int or long because the number could be over 4 billion
digits (in hex). A for loop would do the trick, but I was hoping
someone might know of a different way. Thanks for the thoughts
though.

What Arne was suggesting was an old C trick: looping over the array
one long (64 bits) at a time, negating each long, rather than doing it
a byte at a time. However, as he pointed out, you would have to use
unsafe code to do this.
Thanks for clarifying that. I could do that, but I am trying to avoid
unsafe code. Also, this is a school project and I would get lots of
objections to that.
Thanks for the time guys,
Chris

Feb 13 '07 #5

P: n/a

"Bruce Wood" <br*******@canada.comwrote in message
news:11**********************@p10g2000cwp.googlegr oups.com...
On Feb 12, 2:54 pm, darthgha...@gmail.com wrote:
On Feb 10, 12:05 pm, Arne Vajhøj <a...@vajhoej.dkwrote:
darthgha...@gmail.com wrote:
What would be the most efficient way to calculate the two's complement
of a variable length byte array?
I would assume a for loop negating would be good enough
for most purposes.
You could try negating int or long using unsafe code and
a pointer.
Arne
While working on the native word size of the processor should be faster, it
won't work the way you suggest, because negating (two's complement) is one's
complement which is independent of word size, followed by adding one. That
adding one step won't be done right for simple negation of a wide int, and
adding the right bit pattern (0x01010101) is going to have an unfortunate
tendency to carry from one byte into the next. SIMD (i.e. MMX, SSE or
3DNow!) instructions are your friend.
Feb 13 '07 #6

P: n/a
Ben Voigt wrote:
While working on the native word size of the processor should be faster, it
won't work the way you suggest, because negating (two's complement) is one's
complement which is independent of word size, followed by adding one. That
adding one step won't be done right for simple negation of a wide int, and
adding the right bit pattern (0x01010101) is going to have an unfortunate
tendency to carry from one byte into the next.
You are right. For two's complement we can not change size of items
manipulated.

Can we please bring back ones complement computers.

:-)
SIMD (i.e. MMX, SSE or
3DNow!) instructions are your friend.
Then we just need the asm keyword.

:-)

Arne
Feb 13 '07 #7

P: n/a

"Arne Vajhøj" <ar**@vajhoej.dkwrote in message
news:45***********************@news.sunsite.dk...
Ben Voigt wrote:
>While working on the native word size of the processor should be faster,
it won't work the way you suggest, because negating (two's complement) is
one's complement which is independent of word size, followed by adding
one. That adding one step won't be done right for simple negation of a
wide int, and adding the right bit pattern (0x01010101) is going to have
an unfortunate tendency to carry from one byte into the next.

You are right. For two's complement we can not change size of items
manipulated.

Can we please bring back ones complement computers.

:-)
SIMD (i.e. MMX, SSE or
3DNow!) instructions are your friend.

Then we just need the asm keyword.
In .NET, it would be the jitter's responsibility to apply SIMD instructions
where possible. This might reasonable require some preparation, such as
having the loop unrolled to the right number of simultaneous steps, but I
think the jitter is supposed to do loop unrolling as well.

C++ typically has intrinsic functions for access to advanced instructions,
and some people built template libraries to expose vector classes which use
SIMD for operations, decoding to the native instruction set so the client
code is portable... if C++ can do without inline assembler, then surely C#
can as well since it's Microsoft's gift to the world....
>
:-)

Arne

Feb 13 '07 #8

P: n/a
On Feb 13, 12:34 pm, "Ben Voigt" <r...@nospam.nospamwrote:
"Arne Vajhøj" <a...@vajhoej.dkwrote in message

news:45***********************@news.sunsite.dk...
Ben Voigt wrote:
While working on the native word size of the processor should be faster,
it won't work the way you suggest, because negating (two's complement)is
one's complement which is independent of word size, followed by adding
one. That adding one step won't be done right for simple negation of a
wide int, and adding the right bit pattern (0x01010101) is going to have
an unfortunate tendency to carry from one byte into the next.
You are right. For two's complement we can not change size of items
manipulated.
Can we please bring back ones complement computers.
:-)
SIMD (i.e. MMX, SSE or
3DNow!) instructions are your friend.
Then we just need the asm keyword.

In .NET, it would be the jitter's responsibility to apply SIMD instructions
where possible. This might reasonable require some preparation, such as
having the loop unrolled to the right number of simultaneous steps, but I
think the jitter is supposed to do loop unrolling as well.

C++ typically has intrinsic functions for access to advanced instructions,
and some people built template libraries to expose vector classes which use
SIMD for operations, decoding to the native instruction set so the client
code is portable... if C++ can do without inline assembler, then surely C#
can as well since it's Microsoft's gift to the world....
:-)
Arne
So what you are all saying is that there is no easy way to get a two's
complement of a byte array? That sucks. I guess that's Microsoft's
gift to me?
Thanks again for your time.
Chris

Feb 17 '07 #9

P: n/a
On Feb 16, 8:54 pm, darthgha...@gmail.com wrote:
So what you are all saying is that there is no easy way to get a two's
complement of a byte array? That sucks. I guess that's Microsoft's
gift to me?
I don't know if it's particularly _Microsoft's_ gift to you. More like
the modern Intel processor's gift to you. In fact, I don't think I've
ever worked on a language or a processor in which something as obscure
as taking the two's-complement of a byte array was optimized into some
special instruction or operation.

There's certainly an _easy_ way to do it: loop through the bytes and
take the two's complement of each one. That's pretty darned easy.

However, what you asked for was _faster_. As I said, I've never seen a
_fast_, short-cut way to do that, on any platform, on any chip.
Perhaps others with wider experience have, but not me.

Feb 17 '07 #10

P: n/a
On Feb 16, 11:44 pm, "Bruce Wood" <brucew...@canada.comwrote:
On Feb 16, 8:54 pm, darthgha...@gmail.com wrote:
So what you are all saying is that there is no easy way to get a two's
complement of a byte array? That sucks. I guess that's Microsoft's
gift to me?

I don't know if it's particularly _Microsoft's_ gift to you. More like
the modern Intel processor's gift to you. In fact, I don't think I've
ever worked on a language or a processor in which something as obscure
as taking the two's-complement of a byte array was optimized into some
special instruction or operation.

There's certainly an _easy_ way to do it: loop through the bytes and
take the two's complement of each one. That's pretty darned easy.

However, what you asked for was _faster_. As I said, I've never seen a
_fast_, short-cut way to do that, on any platform, on any chip.
Perhaps others with wider experience have, but not me.
Thanks for the response. That was the way I was hoping to avoid.
Looks like it's the best bet.
Thanks again for the time.
Chris

Feb 17 '07 #11

P: n/a
On Feb 17, 12:16 am, darthgha...@gmail.com wrote:
On Feb 16, 11:44 pm, "Bruce Wood" <brucew...@canada.comwrote:
On Feb 16, 8:54 pm, darthgha...@gmail.com wrote:
So what you are all saying is that there is no easy way to get a two's
complement of a byte array? That sucks. I guess that's Microsoft's
gift to me?
I don't know if it's particularly _Microsoft's_ gift to you. More like
the modern Intel processor's gift to you. In fact, I don't think I've
ever worked on a language or a processor in which something as obscure
as taking the two's-complement of a byte array was optimized into some
special instruction or operation.
There's certainly an _easy_ way to do it: loop through the bytes and
take the two's complement of each one. That's pretty darned easy.
However, what you asked for was _faster_. As I said, I've never seen a
_fast_, short-cut way to do that, on any platform, on any chip.
Perhaps others with wider experience have, but not me.

Thanks for the response. That was the way I was hoping to avoid.
Looks like it's the best bet.
Thanks again for the time.
Chris
Looks like the newest version of Visual Studio will come with a
BigInteger class that I could use. It doesn't support bitwise right
now, but may be they will add it later.
Here's where I saw that:
http://blogs.msdn.com/bclteam/archiv...bar-gazit.aspx

Feb 21 '07 #12

P: n/a
On Feb 20, 8:25 pm, darthgha...@gmail.com wrote:
On Feb 17, 12:16 am, darthgha...@gmail.com wrote:


On Feb 16, 11:44 pm, "Bruce Wood" <brucew...@canada.comwrote:
On Feb 16, 8:54 pm, darthgha...@gmail.com wrote:
So what you are all saying is that there is no easy way to get a two's
complement of a byte array? That sucks. I guess that's Microsoft's
gift to me?
I don't know if it's particularly _Microsoft's_ gift to you. More like
the modern Intel processor's gift to you. In fact, I don't think I've
ever worked on a language or a processor in which something as obscure
as taking the two's-complement of a byte array was optimized into some
special instruction or operation.
There's certainly an _easy_ way to do it: loop through the bytes and
take the two's complement of each one. That's pretty darned easy.
However, what you asked for was _faster_. As I said, I've never seen a
_fast_, short-cut way to do that, on any platform, on any chip.
Perhaps others with wider experience have, but not me.
Thanks for the response. That was the way I was hoping to avoid.
Looks like it's the best bet.
Thanks again for the time.
Chris

Looks like the newest version of Visual Studio will come with a
BigInteger class that I could use. It doesn't support bitwise right
now, but may be they will add it later.
Here's where I saw that:http://blogs.msdn.com/bclteam/archiv...ucing-system-n...
Sorry... still won't work. Again, if you want ones-complement then
this is fine. If you want twos-complement then it won't fly: you have
to take twos-complement byte by byte.

Feb 21 '07 #13

P: n/a

"Bruce Wood" <br*******@canada.comwrote in message
news:11**********************@j27g2000cwj.googlegr oups.com...
On Feb 16, 8:54 pm, darthgha...@gmail.com wrote:
>So what you are all saying is that there is no easy way to get a two's
complement of a byte array? That sucks. I guess that's Microsoft's
gift to me?

I don't know if it's particularly _Microsoft's_ gift to you. More like
the modern Intel processor's gift to you. In fact, I don't think I've
ever worked on a language or a processor in which something as obscure
as taking the two's-complement of a byte array was optimized into some
special instruction or operation.
PSUBSB?

http://asm.inightmare.org/opcodelst/index.php?op=PSUBSB
>
There's certainly an _easy_ way to do it: loop through the bytes and
take the two's complement of each one. That's pretty darned easy.

However, what you asked for was _faster_. As I said, I've never seen a
_fast_, short-cut way to do that, on any platform, on any chip.
Perhaps others with wider experience have, but not me.

Feb 21 '07 #14

P: n/a

"Ben Voigt" <rb*@nospam.nospamwrote in message
news:uA**************@TK2MSFTNGP04.phx.gbl...
>
"Bruce Wood" <br*******@canada.comwrote in message
news:11**********************@j27g2000cwj.googlegr oups.com...
>On Feb 16, 8:54 pm, darthgha...@gmail.com wrote:
>>So what you are all saying is that there is no easy way to get a two's
complement of a byte array? That sucks. I guess that's Microsoft's
gift to me?

I don't know if it's particularly _Microsoft's_ gift to you. More like
the modern Intel processor's gift to you. In fact, I don't think I've
ever worked on a language or a processor in which something as obscure
as taking the two's-complement of a byte array was optimized into some
special instruction or operation.

PSUBSB?

http://asm.inightmare.org/opcodelst/index.php?op=PSUBSB
Sorry, if you want true two's-complement, don't use non-saturating PSUBB

http://asm.inightmare.org/opcodelst/index.php?op=PSUBB

If you want arithmetic negation, PSUBSB more likely serves your purpose.
Feb 21 '07 #15

This discussion thread is closed

Replies have been disabled for this discussion.