Решаем задачу: компьютерные шахматы и вес Хэмминга

Начинающий программист Денис решил написать первый проект — браузерную версию компьютерных шахмат. Сначала все шло отлично — Денис нарисовал доску, где каждая клетка соответствует биту, закрепил отдельные значения за фигурами и написал алгоритм, который следит за происходящим на доске, прописал серверную часть и попробовал запустить приложение.

Спустя некоторое время разработчик заметил, что алгоритм иногда неправильно интерпретирует его действия: после хода фигуры то исчезают с доски, то появляются в неожиданных местах. Почитав форумы, программист выяснил, что проблема может возникать из-за ошибок, которые приводят к потере данных (искажению битов) при передаче пакетов от сервера к клиенту.

Тогда Денис решил добавить функцию проверки потери данных — вес Хэмминга, который по определенной схеме перебирает все биты в пакете и указывает на тот, в котором произошло искажение.

Проблема в том, что Денис никогда не сталкивался с подобными функциями, и решил потренироваться на сравнительно простом примере прежде, чем решать стоящую перед ним задачу.

Содержание

• Условия
• Решение

Условия

Условия примера звучат так:

Число Хэмминга — количество единиц в двоичном представлении числа. Нужно реализовать функцию hammingWeight(), которая принимает целое число в качестве параметра и возвращает вес Хэмминга.

hammingWeight(0); // 0
hammingWeight(4); // 1
hammingWeight(101); // 4

Решение

Эта задача — из испытаний базового курса по Java на Хекслете. С ней справились 89% наших студентов. Ниже опубликован разбор решения — вы можете сравнить свое решение с нашим или посмотреть реализацию, если самостоятельно решить задачу не удается.

Задачу можно решить на нескольких языках программирования — например, на Java или PHP. Ниже опубликован вариант решения на Java, по которому можно воспроизвести определение веса Хемминга.

import java.util.Arrays;
import java.util.List;

public class HammingWeight {
    public static int hammingWeight(int value) {

        int weight = 0;
        List<String> digits = Arrays.asList(Integer.toBinaryString(value).split(""));
        for (String digit : digits) {
            if (digit.equals("1")) {
                weight += 1;
            }
        }
        return weight;
    }
}

О решении этой задачи на PHP на примере код-ревью одного из студентов Хекслета можно почитать здесь.