Prev   Next

UTF-8 ENCODING







Don't practice until you get it right. Practice until you can't get it wrong.

UTF-8 ENCODING

Hey there coder. We begin with the question, "UTF-8 Encoding" in this article.

Reader, we first want you to check out the problem so that you are able to understand its outline.


Important Links : Problem Link, Solution Video


  • You are given an array of n integers. These integers represent the encoding in their binary form.
  • You are required to test whether the array represents a valid sequence of UTF-8 characters or not.
  • As per UTF-8 encoding, a character can be one to four bytes long and according to the length of the character rules are governing UTF-8 encoding:
    1. For a character of length 1 byte, the MSB should always begin with 0.
    2. For a character of length 2 bytes, the starting bits of the upper byte should be 110 and the lower byte should start with 10.
    3. For a character of length 2 bytes, the starting bits of the upper byte should be 1110 and the rest lower bytes should start with 10.
    4. For a character of length 4 bytes, the starting bits of the upper byte should be 11110 and the rest of the lower bytes should start with 10.
  • So to summarize:
    1. Byte -> 0 _ _ _ _ _ _ _
    2. Bytes -> [1 1 0 _ _ _ _ _ ] [1 0 _ _ _ _ _ _ ]
    3. Bytes -> [1 1 1 0 _ _ _ _ ] [1 0 _ _ _ _ _ _ ] [1 0 _ _ _ _ _ _ ]
    4. Bytes -> [1 1 1 1 0 _ _ _ ] [1 0 _ _ _ _ _ _ ] [1 0 _ _ _ _ _ _ ] [1 0 _ _ _ _ _ _ ]
Understanding the Problem:

Let's understand the problem using the following examples.



Example 1:

Sequence -> 11101111, 10111100, 10010111, 11011111, 10000000, 11110010, 10010101, 10001111, 10111111

As this sequence is of type 3 bytes -> 2 bytes -> 4 bytes and abides all rules of UTF-8 encoding henceforth it is a valid sequence.

img
Example 2:

Sequence -> 11101111, 10111100, 10010111, 1011111, 01000000, 11110010, 10010101, 10001111, 10111111



As this sequence is of type 3 bytes ->{redundant} -> 1 byte -> 4 bytes so it fails for byte at index 3rd where we have a redundant byte starting from 10. So this is an invalid sequence.

Approach :
  • The idea behind this problem is to traverse through the entire array and check for every value that whether it lies in 1 byte, 2 bytes, 3 byte, or 4-byte criteria by checking its MSB bits with 0, 110, 1110, and 11110.
  • As per the result, check further (n - 1) bytes for the type where MSB bits starts from 10. Here n represents the byte type, hence n = 1, 2, 3 or 4.
  • If at any instant there occurs an ambiguity then the sequence is not valid.
  • Suppose we need to check whether the given val is of type 3 byte:
    If((val>>4) == 0b1110) => true then it is of type 3 byte
  • Here we have shifted the bits of val 4 sides to the right which makes us consider the last 4 bits of the byte and now if these bits are 1110 then the criteria are met.
  • We can apply this method to check for every type.
CODE

Reader, for the above approach we now write a code as seen below.

import java.io.*; import java.util.*; public class Main { public static boolean solution(int[] arr) { int rbytes=0; //rbytes=remaning bytes for(int val:arr){ if(rbytes==0){ if((val>>7)==0b0){ rbytes=0; }else if((val>>5)==0b110){ rbytes=1; }else if((val>>4)==0b1110){ rbytes=2; }else if((val>>3)==0b11110){ rbytes=3; } }else{ if((val>>6)==0b10){ rbytes--; }else{ return false; } } } if(rbytes==0){ return true; }else{ return false; } } public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int[] arr = new int[n]; for(int i = 0 ; i < n; i++){ arr[i] = scn.nextInt(); } System.out.println(solution(arr)); } }
java; true";

We also suggest you watch the solution video to get an in depth understanding of the code.

Analysis
Time Complexity:

O(n)

Space Complexity:

O(1)


Here, we conclude this problem. If you had any doubts in the discussion, we highly recommend you to watch the solution video of this problem.

We will see you in the next question, ciao.

UTF-8 ENCODING
Bit Manipulation
Author: Shreeya Gupta
 
Run
Id Name