CODEWITHSUNDEEP
bit
tijnn
tijnn

Reputation: 416

How can I check if there is only value changed in a (bitwise?) value?

How can I check if there is only 1 bit change between a value and another (next) value?

the output is for example

001

101

110

in the second output there is a 0 changed into a 1

in the third output there is a 0 changed into a 1 AND also the last 1 changed into a 0

the program may only continue if there is only 1 change.

Upvotes: 3

Views: 4332

Answers (4)

David C. Rankin
David C. Rankin

Reputation: 84579

You can prove it to yourself fairly easily by using an and comparison between an exclusive or of each value and the exclusive or minus 1. It is easier to visualize what takes place by looking at the binary representation of the values and results. Below the function onebitoff performs the test. The other functions just provide a way to output the results:

#include <stdio.h>
#include <limits.h>   /* for CHAR_BIT */

#define WDSZ 64

/** returns pointer to binary representation of 'n' zero padded to 'sz'.
  *  returns pointer to string contianing binary representation of
  *  unsigned 64-bit (or less ) value zero padded to 'sz' digits.
  */
char *cpbin (unsigned long n, int sz) 
{
    static char s[WDSZ + 1] = {0};
    char *p = s + WDSZ;
    int i;

    for (i=0; i<sz; i++) {
        p--;
        *p = (n>>i & 1) ? '1' : '0';
    }

    return p;
}

/* return true if one-bit bitwise variance */
int onebitoff (unsigned int a, unsigned int b)
{
    return ((a ^ b) & ((a ^ b) - 1)) ? 0 : 1;
}

/* quick output of binary difference for 2 values */
void showdiff (unsigned int a, unsigned int b)
{
    if (onebitoff (a, b))
        printf ( " values %u, %u - vary by one-bit (bitwise)\n\n", a, b);
    else 
        printf ( " values %u, %u - vary by other than one-bit (bitwise)\n\n", a, b);

    printf ("  %3u : %s\n", a, cpbin (a, sizeof (char) * CHAR_BIT));
    printf ("  %3u : %s\n", b, cpbin (b, sizeof (char) * CHAR_BIT));
    printf ("  xor : %s\n\n",  cpbin ((a ^ b), sizeof (char) * CHAR_BIT));
}

int main () {

    printf ("\nTest whether the following numbers vary by a single bit (bitwise)\n\n");

    showdiff (1, 5);
    showdiff (5, 6);
    showdiff (6, 1);
    showdiff (97, 105);  /* just as a further test */

    return 0;
}

output:

$ ./bin/bitsvary

Test whether the following numbers vary by a single bit (bitwise)

 values 1, 5 - vary by one-bit (bitwise)

    1 : 00000001
    5 : 00000101
  xor : 00000100

 values 5, 6 - vary by other than one-bit (bitwise)

    5 : 00000101
    6 : 00000110
  xor : 00000011

 values 6, 1 - vary by other than one-bit (bitwise)

    6 : 00000110
    1 : 00000001
  xor : 00000111

 values 97, 105 - vary by one-bit (bitwise)

   97 : 01100001
  105 : 01101001
  xor : 00001000

Upvotes: 0

Krys Jurgowski
Krys Jurgowski

Reputation: 2911

First, XOR the two numbers. XOR will return a 1 for every bit that changed.

Example:

0101110110100100

XOR

0100110110100100

would give you

0001000000000000

Now what you need is a quick way to check if there is only a single bit in your resulting number, or in other words, if the resulting number is a power of two.

A quick test for that is: (x & (x - 1)) == 0.

No for loops needed.

Upvotes: 3

Luis Lavieri
Luis Lavieri

Reputation: 4129

In Java

void main(String[] args){
    boolean value = moreThanOneChanged("101", "001");
}

static boolean moreThanOneChanged(String input, String current){

    if(input.length() != current.length()) return false;

    char[] first = input.toCharArray();

    char[] second = current.toCharArray();

    for(int i = 0, j = 0; i < input.length(); i++){
        if(first[i] == second[i])
            j++;
        if(j > 1)
            return true;
    }

    return false;

}

Upvotes: 0

Manos
Manos

Reputation: 2186

You can compute the bitwise XOR and then just count the bits that are 1's. This is known as the Hamming distance. For example:

unsigned int a = 0b001;
unsigned int b = 0b100;
unsigned int res;
/* Stores the number of different bits */
unsigned int acc;

res = a ^ b;

/* from https://graphics.stanford.edu/~seander/bithacks.html */
for (acc = 0; res; res >>= 1)
{
  acc += res & 1;
}

Upvotes: 0

Related Questions