c++ - Unlimited Unsigned Integer linked-list implementation. Subtraction not working -


so, have implemented entire unlimited unsigned integer class using linked-list project euler problem working on. have verified of logical bit operations correct (though can post if want see them). have implemented operators , operations. however, subtraction (and using it, i.e. division , modulus) doesn't work. when run following test, get:

  limitlessunsigned limitless = 0x88888888u;   limitless = limitless << 4;    limitlessunsigned tester = 0x88888884u;   tester = tester << 4;    //limitless = limitless >> 5;   limitlessunsigned = limitless - tester;

i following values debugger:

    limitlessunsigned    integerlist std::__1::list<unsigned int, std::__1::allocator<unsigned int> >     [0] unsigned int    0b11111111111111111111111111111111 [1] unsigned int    0b00000000000000000000000001000000 limitless   limitlessunsigned    integerlist std::__1::list<unsigned int, std::__1::allocator<unsigned int> >     [0] unsigned int    0b00000000000000000000000000001000 [1] unsigned int    0b10001000100010001000100010000000 tester  limitlessunsigned    integerlist std::__1::list<unsigned int, std::__1::allocator<unsigned int> >     [0] unsigned int    0b00000000000000000000000000001000 [1] unsigned int    0b10001000100010001000100001000000

it seems have missed definition of subtraction , two's compliment. code works until need add 32 bits. accounting overflow, first 32 next 32. however, discarding overflow on highest bit (as thought should). obviously, not doing correctly. below relevant source code.

void limitlessunsigned::sub(const limitlessunsigned& other) {   if(*this <= other)   {     *this = 0u;     return;   }    limitlessunsigned temp = other;      while(temp.integerlist.size() > integerlist.size())     integerlist.push_front(0u);    while(integerlist.size() > temp.integerlist.size())   temp.integerlist.push_front(0u);      temp.twoscomp();     add(temp, true); } void limitlessunsigned::add(const limitlessunsigned& other, bool allowregisterloss) {   limitlessunsigned carry = *this & other;   limitlessunsigned result = *this ^ other;    while(carry != 0u)   {     carry.shiftleft(1, allowregisterloss);     limitlessunsigned shiftedcarry = carry;     carry = result & shiftedcarry;     result = result ^ shiftedcarry;   }   *this = result; }   void limitlessunsigned::not() {     for(std::list<unsigned>::iterator iter = integerlist.begin(); iter != integerlist.end(); ++iter)    {             *iter = ~*iter;          }    }  void limitlessunsigned::twoscomp() {   not();   add(1u, true); }  void limitlessunsigned::shiftleft(unsigned shifts, bool allowregisterloss) {   unsigned carry = 0u;   bool front_carry = false;    while(shifts > 0u)   {         if((integerlist.front() & carry_int_high) == carry_int_high)       front_carry = true;           for(std::list<unsigned>::reverse_iterator iter = integerlist.rbegin(); iter != integerlist.rend(); ++iter)     {            unsigned temp = *iter;        *iter = *iter << 1;       *iter = *iter | carry;               if((temp & carry_int_high) == carry_int_high)         carry = carry_int;       else         carry = 0u;     }      carry = 0u;      if(front_carry && !allowregisterloss)     {       front_carry = false;       integerlist.push_front(1u);     }      --shifts;       } }

update solved problem. here blog post along source code:

http://memmove.blogspot.com/2013/04/unlimited-unsigned-integer-in-c.html

after taking two's complement adding, uses 0 extension when widths not equal. when extend subtrahend (now addend) wide minuend, need use sign extension, not 0 extension. because two's complement value needs treated in context negative number (despite being unsigned elsewhere). alternatively (and perhaps more in keeping overall design), subtrahend , minuend must same width before starting two's complement business.

you're doing this:

0110 - 10 = 0110 + (~(10) + 1)           = 0110 + (01 + 1)           = 0110 + 10           = 0110 + 0010           = 1000

when should be:

0110 - 10 = 0110 + (~(10) + 1)           = 0110 + (01 + 1)           = 0110 + 10           = 0110 + 1110  <= sign-extended subtrahend           = 0100

or alternatively:

0110 - 10 = 0110 - 0010  <= widths equalized           = 0110 + (~(0010) + 1)           = 0110 + (1101 + 1)           = 0110 + 1110           = 0100

Comments

Post a Comment

Popular posts from this blog

Why does Ruby on Rails generate add a blank line to the end of a file? -

running rails generate controller foo home results in: class foocontroller < application controller def home end end (there's nothing on line in actual file, blank line) is there purpose blank line? it's common use newline indicate end of line, last line. many editors (like vi, use) add in newline silently. consensus text files (especially in unix world) should end in newline, , there have been problems historically if wasn't present. why should text files end newline? the tool used count lines in file "wc" counts newlines in file, without trailing newline show 3 instead of 4. it improves readability of templates used in generator. consider: https://github.com/rails/rails/blob/master/railties/lib/rails/generators/rails/controller/templates/controller.rb to remove trailing newline, template have last line of: end<% end -%> instead of: end <% end -%> that seems less readable me. the discussion below refers
Read more

keyboard - Smiles and long press feature in Android -

i've created android keyboard. how add features inserting smilies, , using long keypresses display symbols? to create long-press behavior allows select several options pop-up menu, follow guide (specifically pop-up menu section): http://developer.android.com/guide/topics/ui/menus.html smileys (also known emoticons) combination of keys, understood programs , parsed same way. have do, when clicks smiley face on keyboard, simulate pressing of key combination matching emoticon. example, when clicks smiley, should simulate key presses ':' , ')' :). here's list of emoticons: http://en.wikipedia.org/wiki/list_of_emoticons
Read more

node.js - Bad Request - node js ajax post -

i'm using express 3.0 , node v0.11.0. have button submits form , i'm using ajax post data json object node server. client code is: $('#contact').submit(function(e) { console.log('submit called'); var formdata = json.stringify($('form').serializeobject()); console.log(formdata); $.ajax({ url: "http://localhost:3000/savedata/", type: "post", datatype: 'json', data: {objectdata: formdata}, contenttype: "application/json", complete: function() { console.log('process complete'); }, success: function(data) { console.log('process sucess'); }, error: function() { console.log('process error'); }, }); return false; }); then on server: var express = require('express'); var app = express(); app.set('views', __dirname + '/views'); app.set('view engine', 'jade'); app.use(express.bodyparser());
Read more