Thread: Palindromes and Bitwise operators

  1. #1
    Registered User
    Join Date
    Aug 2007
    Posts
    2

    Palindromes and Bitwise operators

    Hi,

    I've been learning to use the bitwise operators and i've been doing some exercises without problems until i came across with this one:

    "write a program that finds USING BITWISE OPERATORS whether a number entered by the user is a palindrome or not"

    Does anyone have any idea of how to do it?

  2. #2
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Dr Tornillo View Post
    "write a program that finds USING BITWISE OPERATORS whether a number entered by the user is a palindrome or not"
    A palindrome in which base? If binary, it's easy. If decimal, it's stupidly difficult.

  3. #3
    Registered User
    Join Date
    Aug 2007
    Posts
    2
    decimal…
    yes, I know that it's quite difficult and that it doesn't have much sense to do it that way

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Dr Tornillo View Post
    decimal…
    yes, I know that it's quite difficult and that it doesn't have much sense to do it that way
    Well, you'd have to implement division and modulo by 10 using bitwise operators. Once you have that, the rest is cake.

    But personally, I think it's a silly exercise. I think you'll gain a bunch of frustration, not understanding.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If it's binary, then it's dead easy, as brewbuck says: Just shift out a number down one side, and pick the bits up into a new number. If the two numbers match, it's a palindrome. For example 5, 6, 9, 27 are binary palindromes.

    Doing divide/modulo in base 10 with only shifts and logical operations seem difficult (but obviously possible, because "and" and "or" is nearly the only thing that is available in transistor logic, so that's how a processor would do add, subtract, multiply, etc - but there are a lot of transistors in a modern processor just because it's so complicated to do these things with just these simple operations).

    --
    Mats

  6. #6
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    How is 6 ( 110) a palindrome?

  7. #7
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Put a 0 on the front. lol.... Sorry, you asked.

  8. #8
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    Bitwise operations are necessary for much low-level programming, such as writing device drivers, low-level graphics, communications protocol packet assembly and decoding.

    Although machines often have efficient built-in instructions for performing arithmetic and logical operations, in fact all these operations can be performed just by combining the bitwise operators and zero-testing in various ways. For example, here is a pseudocode example showing how to multiply two arbitrary integers a and b using only bitshifts and addition:

    c := 0
    while b ≠ 0
    if (b and 1) ≠ 0
    c := c + a
    shift a left by one
    shift b right by one

    return c
    --Wikipedia example in psuedocode
    Link to article: http://en.wikipedia.org/wiki/Bitwise_operation
    I assume divide is just the reverse?
    Last edited by manofsteel972; 08-02-2007 at 03:47 PM. Reason: included direct link to Wikipedia article to comply with wikipedia copyright rules
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by manofsteel972 View Post
    I assume divide is just the reverse?
    The code you showed uses "+" to add... :-)

    And yes, divide is similar in that you shift, but you also need to compare (but perhaps that CAN be done with a and operation).

    --
    Mats

Popular pages Recent additions subscribe to a feed