KR1shna's blog

By KR1shna, history, 15 months ago, In English


Let x is in binary and its gray code is y;
Then this can be shown that y = x^(x>>1)
Before proving this we would like to show that we can also recover x from gray code y as follow;
Let us observe that (y>>1) = (x>>1)^(x>>2), 
Similarly (y>>i) = (x>>i)^(x>>(i+1))
Therefore x = x ^ (x>>1) ^ (x>>1) ^ (x>>2) ^ (x>>2) ^ … ^ (x>>(n-1)) ^ (x>>n)
Where 2^n > x, 
Thus x = y ^ (y>>1) ^ (y>>2) ^ (y>>(n-1))
/*
Now, let us focus how to prove y =  x ^ (x>>1)
It is enough for us to prove that if y is such then hamming distance between y and y+1 is 1 (Gray code definition). 
So, let us focus on the numbers from 0 to 2^n-2 (inclusive) , (we have excluded 2^n-1 because there is no further element to check I.e. 2^n-1+1 is 2^n overflow).
As we said our number x is between 0 to 2^n-2, then there exist at least one zero bit in its binary representation. Let us write that ,
*/
x = bz … b(t+2) 0  1 1 1 1 1… 1
Then let 0 is right most of all 0’s, at t_th position where 0<=t<=z
Now x+1 = bz … b(t+2) 1 0 0 0 0 0 … 0


 x       = bz b(z-1)… b(t+2)    0    1 1 1 1 1.. 1 
 x>>1    = 0   bz   … b(t+3) b(t+2)  0 1 1 1 1.. 1
----------------------------------------------------
 y(xor) = cz c(z-1) … c(t+2)  c(t+1) 1 0 0 0.. 0 0

/* So let us covert each x and x+1 to its corresponding y and y1 .

Where cz= bz, c(z-1)= bz ^ b(z-1), and so on, at the end c(t+1) = b(t+2)
*/
Similary,
x         = bz b(z-1).. b(t+2)    1    0 0 0 0 0.. 0
x>>1      = 0   bz  ..  b(t+3) b(t+2)  1 0 0 0 0.. 0
--------------------------------------------------------
y1(xor)  = cz c(z-1) … c(t+2)  c’(t+1) 1 0 0 0 0.. 0
/*
We observe that only bit at t+1_th position changes all remains the same 
c’(t+1) = 1 ^ b(t+2) = negation (b(t+2)) 
And c(t+1) = b(t+2) 
Thus hamming distance is 1.*/

———-That’s it————

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By KR1shna, history, 20 months ago, In English

My first blog. Seeking some positive feedback
It might be useful to some of us
Introduction:
Before a C++ program gets compiled by the compiler, the source-code gets processed by the compiler. This technique is called preprocessor.
This technique is not a part of the compiler but it is a separate method that comes under compilation process. It directs the compiler that the information should be preprocessed before the actual compilation starts.
All preprocessor directives in C++ begin with #, and they do not need to end with a semicolon(;) because this is not a statement in C++.
Imagw
Look at the following piece of code in C++:

 
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define macro1
#define macro2
...
#include "local_header1.h"
#include "local_header2.h"
...
#endif
//.....//
#ifndef stands for if_not_defined

#ifdef stands for if_defined

One can use preprocessor directives to make more debugs through your local device.
One can define some specific header files only to be used in local device not on online_judge
One can use macro as flags inside these #ifndef or #ifdef containers

Examples:
(1)

 
#ifndef ONLINE_JUDGE
#define covid19 text
#endif

#ifdef covid19
cout<<"Yes, its corona";
#endif
(Here, we used covid19 as flag to print something.)
(2)
Thanks to Errichto as I learned from him on YouTube
https://github.com/Errichto/youtube/blob/master/atcoder-dp/g.cpp
(You can see on the above link he used #ifdef LOCAL for debugging, this will print stuffs local to the device)

For more information consider the following links
https://gcc.gnu.org/onlinedocs/cpp/Macros.html
https://en.wikipedia.org/wiki/C_preprocessor

Image source https://www.w3schools.in/cplusplus-tutorial/preprocessor/

Read more »

 
 
 
 
  • Vote: I like it
  • +35
  • Vote: I do not like it